首页 > 代码库 > [BZOJ1029] [JSOI2007]建筑抢修（贪心 + 优先队列）
[BZOJ1029] [JSOI2007]建筑抢修（贪心 + 优先队列）
传送门
把数据存在结构体中，至于怎么贪心？
肯定会有些想法，正确错误先不必说，先来试一试。
1.按照 t2 为第一关键字从小到大排，按照 t1 为第二关键字从小到大排
这个显然错，比如后面有个数的 t1 比前面小，t2 比前面大，显然用这个代替前面的更优
2.按照 t1 为第一关键字从小到大排，按照 t2 为第二关键字从小到大排
这个也是错的，比如
4
1 1
1 5
3 4
4 5
按照这个贪心是 2，实际应该是 3
至于正确贪心，如果 当前时间 + t1[i] <= t2[i]，说明可以建完，ans++，并把 t1 放入大根堆
如果 当前时间 + t1[i] > t2[i]，说明不能建，那么把当前的 t1[i] 和堆顶比较
如果 > 堆顶，continue
如果 < 堆顶，如果 当前时间 - 堆顶 + t1[i] <= t2[i]，说明拿它替换堆顶更优，那么就替换，ans++
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 5 int n, time, ans; 6 struct node 7 { 8 int a, b; 9 }p[150001];10 std::priority_queue <int> q;11 12 inline bool cmp(node x, node y)13 {14 return x.b < y.b;15 }16 17 int main()18 {19 int i;20 scanf("%d", &n);21 for(i = 1; i <= n; i++) scanf("%d %d", &p[i].a, &p[i].b);22 std::sort(p + 1, p + n + 1, cmp);23 for(i = 1; i <= n; i++)24 {25 if(time + p[i].a <= p[i].b)26 {27 time += p[i].a;28 ans++;29 q.push(p[i].a);30 }31 else if(p[i].a < q.top())32 {33 if(time - q.top() + p[i].a <= p[i].b)34 {35 time = time - q.top() + p[i].a;36 q.pop();37 q.push(p[i].a);38 }39 }40 }41 printf("%d", ans);42 return 0;43 }
我真是菜啊，错误的贪心都举不出来反例，只有对拍出来。
[BZOJ1029] [JSOI2007]建筑抢修（贪心 + 优先队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。