#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
const int rht = 1000000;
const int MAX_N = 50000;
typedef pair<int, int> Interval;/*left, eight*/
typedef pair<int, int> Id_Stall;/*id, stall No.*/
typedef pair<int, int> Stall/*start, stall No.*/;
typedef pair<Interval, Id_Stall> Cow;
typedef priority_queue<Stall, vector<Stall>, greater<Stall> > PQ;
int main() {
	int N;
	while(scanf("%d", &N)!=EOF){
		Cow cows[MAX_N];
		for(int i = 0;i<N;i++){
			scanf("%d%d", &cows[i].first.first, &cows[i].first.second);
			cows[i].second.first = i;
		}
		sort(cows, cows+N);
		int s_cnt = 1;
		PQ q_stall; 
		q_stall.push(Stall(cows[0].first.second+1, s_cnt));
		cows[0].second.second = s_cnt;
		for(int i = 1;i<N;i++){
			if(q_stall.top().first > cows[i].first.first){
				q_stall.push(Stall(cows[i].first.second+1, ++s_cnt));
				cows[i].second.second = s_cnt;
			}
			else{
				Stall tmp = q_stall.top();
				q_stall.pop();
				tmp.first = cows[i].first.second + 1;
				q_stall.push(tmp);
				cows[i].second.second = tmp.second;
			}
		}
		int s_no[MAX_N];
		for(int i = 0;i<N;i++)
			s_no[cows[i].second.first] = cows[i].second.second;
			
		printf("%d\n", s_cnt);
		for(int i = 0;i<N;i++)
			printf("%d\n", s_no[i]);
	}
	return 0;
}

• Re:排序+堆+贪心，新人水贴 (3) zhaohaikun 2020-01-16 14:50:00
  • Re:排序+堆+贪心，新人水贴 (7) lhdhl 2020-04-07 20:51:46