ABC 127 D -Integer Cards

atcoder.jp

問題概要

N枚のカードが与えられ、それぞれAiという数字が与えられる。
M種類の操作を自由に行い、与えられたカードの数字を最大化してください。

・操作：B枚のカードまで数字Cに書き換えられる。（0枚でも良い）

考えたこと

操作は行わなくても良い、また、元の数字より低い数字に書き換える必要はない。さらに、何を書き換えたかはどうでもよく、操作後の合計値だけ知りたい。
という条件のもと、N枚のカードを最大化したければ、登場した数字のうち大きい順にN個選択すれば良い。
なぜなら、今あるカードをより高い数字で更新し続けるのが明らかに最適だからで、これは直感的にも正しそう。
因みにこれはABC121 Cと同じ問題と言える。

C - Energy Drink Collector

実装

操作は自由に行ってよいので、与えられた操作の条件を、Cが書かれたB個のカードとして扱うことができる。
元あったカードは、個数1、数値Aiのカードとする。
これらを大きい順に選択していき、取りすぎた分があれば元に戻せばよい。

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

int main(void){
	ll n,m;
	cin>>n>>m;
	ll a[n];
	vector<pair<ll,ll>>ans;
	for(int i=0;i<n;i++){
		cin>>a[i];
		ans.push_back(make_pair(a[i],1LL)); //元あったカードを個数1のペアにする
	}
	ll b[m],c[m];
	for(ll i=0;i<m;i++){
		cin>>b[i]>>c[i];
		ans.push_back(make_pair(c[i],b[i])); //与えられた操作をカードとして扱う
	}
	sort(ans.begin(),ans.end(),greater<pair<ll,ll>>()); //降順にソート
	ll res =0;ll num=0; //resが答えで、numは選択したカードの枚数
	for(ll i=0;i<m+n+10;i++){
		res += ans[i].first * ans[i].second; //CをB個一気に取得
		num += ans[i].second; //B個取得したことをメモ
               //n枚ちょうどなら終了、取りすぎたならその分戻して終了
		if(num==n){
			break;
		}else if(num>n){
			res -= ans[i].first*(num-n);
			break;
		}
	}
	cout<<res<<endl;
}