【AtCoder】ABC 360 C - Move It | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 36

問題概要

$1$ から $N$ までの番号が付いた箱と荷物がある。荷物 $i \: (1 \leq i \leq N)$ は箱 $A_i$ の中にあり、重さは $W_i$ である。ここで、「荷物を一つ選び、他の箱の中に移動させる操作」を0回以上繰り返し行う。ただし、1回の操作で移動させる荷物の重さが $w$ であるとき、 $w$ のコストがかかる。全ての箱に荷物が1つずつ入っている状態にするためにかかるコストの総和の最小値を求めよ。

制約

入力はすべて整数。
$1 \leq N \leq 10^5$
$1 \leq A_i \leq N$
$1 \leq W_i \leq 10^4$

考察

まず、「全ての箱に荷物を1個ずつ入れる」という条件を満たすために、2個以上の荷物が入った箱については、1個だけ箱に残して他は別の箱に移動させる必要がある。

また、コストを最小化したいので、残すべき荷物は重さが最も重いものでなければならない。

したがって、コストの最小値は「各箱に入った荷物の重さの総和から最も重い荷物の重さを除いたものの合計」で求めることができる。

実装においては、max_w[i] $:= i \text{番目の箱に入っている荷物の中で最も重いものの重さ}$ という配列を作ることで簡単になる。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N), W(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> W[i];

    vector<int> max_w(N, 0);
    rep(i, 0, N) chmax(max_w[A[i] - 1], W[i]);

    int sum = 0;
    rep(i, 0, N) sum += W[i];
    rep(i, 0, N) sum -= max_w[i];

    cout << sum << endl;
}