混ぜてソートは賢すぎる!!!惚れた!!!
問題概要
枚のカードにそれぞれ の数値が書かれている。あなたは、 について順に以下の操作を 1 回ずつ行います。
- カードを 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ に書き換える。
操作終了後のカードの数値の総和の最大値を求めよ。
制約条件
考えたこと 1
ややこしいけど、こういうのはちゃんと順を追って考えれば行ける。とりあえず思うのは
- もともとが小さいやつを優先的に書き換えたい
- なるべく大きいやつに書き換えたい
このあたりのことをきちんと整理しながら考える。具体的には「変数を固定して考える」という戦略が良さそうに思える。まず、 枚のカードのうち 枚を書き換えるとすると、
- のうち小さい順に 枚を書き換える
- のうち大きい順に 枚を書き換える
とすればよいことがわかる。まとめると
- を小さい順にソート
- を大きい順にソート
- 各 に対して、 ( の 番目, の 番目) を合計
したものが答えになる。ただし、 の個数が に満たない場合は、足りない部分は単純に の方を足していく。
#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std; using pll = pair<long long, long long>; int main() { int N, M; cin >> N >> M; vector<long long> A(N), B(M), C(M); for (int i = 0; i < N; ++i) cin >> A[i]; sort(A.begin(), A.end()); B.resize(M); C.resize(M); for (int i = 0; i < M; ++i) cin >> B[i] >> C[i]; // C をソート (B をまとめて) vector<int> id(M); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int i, int j) { return C[i] > C[j];}); // A (小さい順) と C (大きい順) とを比べて大きい方を足していく long long sum = 0; long long K = 0; for (auto i : id) { for (int j = 0; j < B[i]; ++j) { if (K >= N) break; sum += max(A[K++], C[i]); } } for (int i = K; i < N; ++i) sum += A[i]; cout << sum << endl; }
解法 2
実はすごく簡単に
を全部混ぜて大きい順に 個とった合計値で OK。このとき全部混ぜたものの個数は になってまともに扱えないが、ランレングス圧縮した世界で考えれば OK。
#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std; using pll = pair<long long, long long>; int main() { int N, M; cin >> N >> M; vector<pll> v; for (int i = 0; i < N; ++i) { int a; cin >> a; v.push_back({a, 1}); } for (int i = 0; i < M; ++i) { int b, c; cin >> b >> c; v.push_back({c, b}); } sort(v.begin(), v.end(), greater<pll>()); long long num = 0; long long res = 0; for (auto p : v) { if (num + p.second <= N) { res += p.first * p.second; num += p.second; } else { res += p.first * (N - num); num = N; break; } } cout << res << endl; }