传送门
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）
下一篇：[luoguP2387] 魔法森林（LCT + 并查集）
并查集 stl 贪心 堆
