Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 排序+堆+贪心，新人水贴

Posted by scissorsy at 2016-01-06 16:23:06 on Problem 3190
```#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;
}```

Followed by: