Codeforces #241 Div2 C. Booking System

CF#241に参加。
一応時間内に全部解けたかと思ったら、アプローチはよかったものの詰めが甘くEを落とした
とはいえDiv2込みで過去最高の出来かも。
http://codeforces.com/contest/416/problem/C

問題

K個のテーブルがあるレストランがあり、各テーブルの椅子の数R[i]が与えられる。
ここにN組の集団が現れる。
各集団はC[i]人で構成され、P[i]だけお金を払ってくれる。

各テーブルは、椅子の数以下の人数で構成される１つの集団のみ利用することができる。
テーブルにつけないグループは当然店を利用できず、お金を払ってくれない。

どの集団をどのテーブルに割り当てることでお店の儲けを最大化出来るか答えよ。

解法

払ってくれる金額が多い集団の順にテーブル割り当てを考える。
その際、集団の人数以上のうち最小の椅子のテーブルを割り当てればよい。

int N;
int C[1001],P[1001];
int K;
vector<pair<int,int> > PP;
vector<pair<int,int> > T;
int sit[1001],done[1001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>C[i]>>P[i];
		PP.push_back(make_pair(P[i],i));
	}
	
	sort(PP.begin(),PP.end());
	cin>>K;
	FOR(i,K) {
		cin>>x;
		T.push_back(make_pair(x,i));
	}
	sort(T.begin(),T.end());
	reverse(PP.begin(),PP.end());
	
	MINUS(sit);
	int ma=0,tot=0;
	FOR(i,N) {
		FOR(j,K) if(done[j]==0) {
			if(C[PP[i].second]<=T[j].first) break;
		}
		if(j<K) {
			done[j]=1;
			ma++;
			tot+=PP[i].first;
			sit[PP[i].second]=T[j].second;
		}
	}
	
	_P("%d %d\n",ma,tot);
	FOR(i,N) if(sit[i]>=0) _P("%d %d\n",i+1,sit[i]+1);
}

まとめ

まだまだ簡単。