[AtCoder] ABC 127 D – Integer Cards
問題
方針
実際にカードを書き換えていく方法は計算量が多くなるので、最終的なカードの値を考えていきます。
ある操作でカードを書き換えるのではなく、カードが増えたとして、上から \( N \) 枚選び、その和が答えになります。ここで、マップを考えます。キーにカードの取りえる値、バリューにカードの枚数を保持するようなマップをキーの降順になるように並び替えます。
全体として、カードが
\[ N + \displaystyle \sum_{i=1}^{M} B_i\]
枚あるイメージですね。
コード
提出したコード
マップによるカードの管理
map<ll, ll, greater<ll>> m; for (int i = 0; i < N; i++) { m[A[i]]++; } for (int i = 0; i < M; i++){ m[C[i]] += B[i]; } ll ans = 0; ll cnt = 0; for (auto i = m.begin(); i != m.end(); i++) { if (cnt > N) break; if (cnt + i -> second >= N) { ans += (N - cnt) * i -> first; break; } else { ans += i -> second * i -> first; cnt += i -> second; } }
ディスカッション
コメント一覧
まだ、コメントがありません