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

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

思路：先對結構體x升序y升序，再對優先隊列重載<，按y升序。

　　然后依次入隊，如果node[i].x<=q.top().y ans++， 否則出隊，入隊，使用出隊的那個攤位。

1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<set> 8 #define INF 0x3f3f3f3f 9 typedef long long ll; 10 using namespace std; 11 struct Node{ 12 int x, y; 13 int id; 14 bool operator<(const Node &a)const{ 15 return y > a.y; 16 } 17 }node[50010]; 18 int n, maxm = -INF, b[50010]; 19 bool cmp(const Node a, const Node b) 20 { 21 if(a.x != b.x) 22 return a.x<b.x; 23 return a.y<b.y; 24 } 25 int main() 26 { 27 scanf("%d", &n); 28 int ans = 1; 29 for(int i = 0; i < n; i++){ 30 scanf("%d%d", &node[i].x, &node[i].y); 31 node[i].id=i+1; 32 } 33 sort(node, node+n, cmp); 34 priority_queue<Node> q; 35 q.push(node[0]); 36 b[node[0].id] = ans; 37 for(int i = 1; i < n; i++){ 38 Node t = q.top(); 39 if(node[i].x <= t.y){ 40 q.push(node[i]); 41 ans++; 42 b[node[i].id] = ans; 43 //maxm = max(maxm, ans); 44 } 45 else if(node[i].x > t.y){ 46 q.pop(); 47 q.push(node[i]); 48 b[node[i].id] = b[t.id]; 49 //cout << b[t.id] << "t"; 50 } 51 } 52 printf("%d\n", ans); 53 for(int i = 1; i <= n; i++){ 54 printf("%d\n", b[i]); 55 } 56 57 return 0; 58 }

?

轉載于:https://www.cnblogs.com/Surprisezang/p/9000363.html

總結

以上是生活随笔為你收集整理的poj3190 Stall Reservations（贪心+STL）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。