[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）

传送门

1.贪心 + 优先队列

按照时间排序从前往后

很简单不多说

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 #define N 10001 6 7 int n, t, ans; 8 std::priority_queue <int, std::vector <int>, std::greater <int> > q; 9 10 struct node 11 p[N]; 14 15 inline int read() 16 23 24 inline bool cmp(node x, node y) 25 28 29 int main() 30 47 else if(t == p[i].b + 1 && q.top() < p[i].a) 48 53 } 54 printf("%d\n", ans); 55 } 56 return 0; 57 }
View Code

2.并查集

很难想

按照价格从大到小排序

如果当前的那一天没有被占用，那么就用当前那一天，如果当前那一天被占用了，就用上一天，如果还被占用，再往前

其实这就是暴力过程

可以用并查集优化，当前天被占用时用并查集连接上一天，如果根指向0，就表明前面的天都被占用了，也就不用加

具体看代码

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define N 10001 5 6 int n, ans; 7 int f[N]; 8 9 struct node 10 p[N]; 13 14 inline bool cmp(node x, node y) 15 18 19 inline int find(int x) 20 23 24 inline int read() 25 32 33 int main() 34 50 } 51 printf("%d\n", ans); 52 } 53 return 0; 54 }
View Code

上一篇：[BZOJ2843] 极地旅行社（LCT）

下一篇：[POJ3162]Walking Race（DP + 单调队列）

---

stl 贪心 并查集 堆