poj3190 Stall Reservations（贪心+STL）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

https://vjudge.net/problem/POJ-3190

cin和scanf差这么多么。。tle和300ms

思路：先对结构体x升序y升序，再对优先队列重载<，按y升序。

然后依次入队，如果node[i].x<=q.top().y ans++，否则出队，入队，使用出队的那个摊位。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
struct Node{
int x, y;
int id;
bool operator<(const Node &a)const{
return y > a.y;
}
}node[];
int n, maxm = -INF, b[];
bool cmp(const Node a, const Node b)
{
if(a.x != b.x)
return a.x<b.x;
return a.y<b.y;
}
int main()
{
scanf("%d", &n);
int ans = ;
for(int i = ; i < n; i++){
scanf("%d%d", &node[i].x, &node[i].y);
node[i].id=i+;
}
sort(node, node+n, cmp);
priority_queue<Node> q;
q.push(node[]);
b[node[].id] = ans;
for(int i = ; i < n; i++){
Node t = q.top();
if(node[i].x <= t.y){
q.push(node[i]);
ans++;
b[node[i].id] = ans;
//maxm = max(maxm, ans);
}
else if(node[i].x > t.y){
q.pop();
q.push(node[i]);
b[node[i].id] = b[t.id];
//cout << b[t.id] << "t";
}
}
printf("%d\n", ans);
for(int i = ; i <= n; i++){
printf("%d\n", b[i]);
} return ;
}