PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes
DIFFICULTY:
Easy
PREREQUISITES:
Sorting
PROBLEM:
There are n cars on a circular track of length n, the i-th of them is on clockwise distance i-1 from the car 1.
You can fill the i-th car with at most f_i litres of gasoline and pay c_i coins for each litre. Then you choose one of the cars, and start driving clockwise, the car spends one litre of gasoline per unit of distance. When you pass through another car, you steal all its gasoline.
Fill the cars with the minimum cost in such a way, that is possible to choose a car and travel a distance n clockwise.
QUICK EXPLANATION:
Greed is good: Iterate over the cars in non-decreasing order of cost and greedily fill it with the maximum possible (and necessary) litres of gasoline.
EXPLANATION:
Let’s suppose that the i-th car is filled with q_i litres of gasoline, the necessary and sufficient conditions to be able of driving a full circle are:
- q_i \leq f_i
- q_1 + q_2 + ... + q_N = N
If the second condition is not quite clear, you can imagine that buying a litre of gasoline from the i-th car creates a bridge of length one between positions i and i+1. If one bridge intersects another one, it pushes it clockwise. In order to drive a full circle we need N bridges.
The cost expended in the i-th car is q_i \cdot c_i, so we are asked to minimize P=q_1 \cdot c_1 + q_2 \cdot c_2 + ... + q_n \cdot c_n.
Intuitively we should try to use the maximum litres of gasoline from the cheapest cars.
Let’s fill the cars with gasoline in increasing order of cost. Suppose that we already purchased optimally G litres of gasoline from the i cheapest cars. How much gasoline should we buy from car i+1?
- If G \geq N, we have enough gasoline, so we don’t have to buy more.
- Otherwise, we can buy at most g = min(f_i, N-G) litres of gasoline. Should we buy all the g litres? Yes, if we buy one unit less, then that unit will be purchased from another more expensive (or at least not cheaper) car!
SOLUTIONS:
Setter's Solution
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <int> f(n),c(n);
for (int i = 0; i < n; i++) {
cin >> f[i];
}
vector <pair <int, int> > e;
for (int i = 0; i < n; i++) {
cin >> c[i];
e.push_back({c[i], f[i]});
}
sort(e.begin(), e.end());
int sum = 0;
ll ans = 0;
for (auto c : e) {
if (sum + c.second <= n) {
sum += c.second;
ans += c.first * (ll) c.second;
} else {
ans += (n - sum) * (ll) c.first;
break;
}
}
cout << ans << '\n';
}
}
Tester's Solution
void solve() {
int n;
cin >> n;
vector<int> arr;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
arr.push_back(num);
}
vector<int> cost;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
cost.push_back(num);
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return cost[a] < cost[b];
});
ll ans = 0;
int left = n;
for (int pos : order) {
int val = min(left, arr[pos]);
left -= val;
ans += (ll) val * cost[pos];
if (!left) {
break;
}
}
cout << ans << "\n";
}
