CODE FESTIVAL 2014 あさプロMiddle : B - 枕決め

まだまだ。
http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_d

問題

N人の人とM個の枕がある。
N人はそれぞれ高さがX[i]以上Y[i]以下の枕が好みであり、そのような枕を１個使いたい。
M個の枕の高さA[i]が与えられるとき、最大何人が好みの枕を使えるか。

解法

Codeforcesで良く出てくるタイプの問題。
まず各人の番号をX[i]ごとに配列に入れる。

次に高さの下限1から上限100000まで以下の処理を行う。今見ている高さをhとすると：

• 最初に作った配列を参照し、X[i]==hであるような人がいたら(Y[i],i)のペアpriority_queueに入れる。
• priority_queueを見て、Y[i]
• A[i]==hな枕の数だけ、priority_queueからY[i]の低い順に枕を割り当てる。

priority_queueには「h以上の枕が好みの人が、Y[i]の低い順に入っている」という状態にしておくことで、以後登場する枕をY[i]の低い順に割り当てることができる。

int N,M;
vector<int> P[100001];
int MN[100001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		P[x].push_back(y);
	}
	
	FOR(i,M) cin>>x, MN[x]++;
	priority_queue<int> Q;
	
	int ret=0;
	FOR(i,100001) {
		FOR(x,P[i].size()) Q.push(-P[i][x]);
		while(Q.size() && -Q.top()<i) Q.pop();
		FOR(j,MN[i]) {
			if(Q.size()) ret++, Q.pop();
		}
	}
	cout<<ret<<endl;
}

まとめ

このテクも知らないとちょっときついよね。