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

## 双优先队列水过。。。。。。

Posted by Golden_echo at 2019-07-28 11:04:08 on Problem 3190
```#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <ctype.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <math.h>
#include <map>
#include <list>
#include <ctime>
#include <limits>

using namespace std;

typedef pair<int,int> P;
struct Cow{
P time;
int id;
bool operator >(const Cow &b) const{
return time>b.time;
}
};

struct Stall{
int id,last;
Stall(){
id=0,last=0;
}
Stall(int i,int l){
id=i,last=l;
}
bool operator <(const Stall &b) const{
return this->last>b.last;
}
};

class Stalls{
public:
priority_queue <Stall ,vector<Stall> >  stalls;

int push(const Cow &c){
int num;
if(stalls.empty()){
Stall s(1,c.time.second);
num=1;
stalls.push(s);
}
else{//先要找出第一个，分可以和不可以两种
Stall best_one=stalls.top();
stalls.pop();
if(best_one.last<c.time.first){
best_one.last=c.time.second;
stalls.push(best_one);
num=best_one.id;
}
else{
stalls.push(best_one);
num=stalls.size()+1;
Stall s(num,c.time.second);
stalls.push(s);
}
}
return num;
}
};

int main() {
int n;
while(scanf("%d",&n)!=EOF) {
Cow c;
Stalls ss;
int *ans=new int[n];
priority_queue<Cow,vector<Cow> ,greater<Cow> > cows;
for (int i = 0; i < n; i++) {
scanf("%d %d",&c.time.first,&c.time.second);
c.id=i;
cows.push(c);
}
while(cows.empty()==0){
Cow c =cows.top();
ans[c.id]=(ss.push(c));
cows.pop();
}

cout << ss.stalls.size() << endl;
for (int i = 0; i <n; i++) {
cout << ans[i] << endl;
}
}
return 0;
}```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator