Official

F - Move It Editorial by en_translator


In order to have exactly one item for every box, for all boxes with two or more items, we need to leave only one of it there and move the others.

Let \(w_1,\ldots,w_{k}\) be the weights of the \(k\) items \((2\leq k)\) in box \(i\) with two or more items; then the minimum total weight of the items required to be moved is \(\sum_{i=1}^{k}w_i - max(w)\). Thus, in order to have exactly one item for every box, the minimum total cost required is the sum of this value over al boxes with two or more items.

This minimum value is achievable. Since there are \(K\) boxes and items, the number of items that have to be moved equals that of boxes. Therefore, one can move the items to be moved to an empty box so as to have exactly one item for every box.

When implementing, one can answer by managing the maximum weight of an item in each box, and subtracting their sum from the total weight of the \(N\) items.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), w(n);
    vector<int> max_weight(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> w[i];

    for (int i = 0; i < n; ++i){
        a[i]--;
        max_weight[a[i]]=max(max_weight[a[i]],w[i]);
    }

    const int sum_w=accumulate(w.begin(),w.end(),0);
    const int sum_max=accumulate(max_weight.begin(),max_weight.end(),0);
    cout << sum_w-sum_max << endl;
}

posted:
last update: