BZOJ 1029: [JSOI2007]建筑抢修（贪心）

2021-06-06 22:01

阅读：357

标签：stream images ima 分享 color while bsp pll set

http://www.lydsy.com/JudgeOnline/problem.php?id=1029

题意：

技术分享

思路：
先按T2排序，并维护一个T1的优先队列，然后对于每个建筑，如果当前这个建筑能修的话，那么就修。如果不能修，那么就从优先队列中弹出之前的建筑中所需修复最长的时间，如果该时间比我当前建筑时间还长并且去掉它后就能修理当前建筑，那么我们就放弃那个，改为修理当前建筑，因为这样一来总的时间会更小。

 1 #include 2 #include
 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include10 #include11 #includeset>
12 using namespace std;
13 typedef long long ll;
14 typedef pairint,ll> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn=50000+5;
17 
18 int n;
19 
20 struct node
21 {
22     int cost,end;
23 }a[150005];
24 
25 bool cmp(node a, node b)
26 {
27     return a.endb.end;
28 }
29 
30 bool operator b)
31 {
32     return a.cost>b.cost;
33 }
34 
35 int main()
36 {
37     //freopen("in.txt","r",stdin);
38     while(~scanf("%d",&n))
39     {
40         for(int i=1;i"%d%d",&a[i].cost,&a[i].end);
41         sort(a+1,a+1+n,cmp);
42         priority_queueint> Q;
43 
44         int t=0;
45         int ans=0;
46         for(int i=1;i)
47         {
48             if(t+a[i].costa[i].cost;Q.push(a[i].cost);}
49             else
50             {
51                 if(t-Q.top()+a[i].cost=a[i].cost)
52                 {
53                     t=t-Q.top()+a[i].cost;
54                     Q.pop();
55                     Q.push(a[i].cost);
56                 }
57             }
58         }
59         printf("%d\n",ans);
60     }
61     return 0;
62 }

BZOJ 1029: [JSOI2007]建筑抢修（贪心）

标签：stream images ima 分享 color while bsp pll set

原文地址：http://www.cnblogs.com/zyb993963526/p/7337310.html

上一篇：Spring要点

下一篇：node.js学习笔记一

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ 1029: [JSOI2007]建筑抢修（贪心）
文章链接：http://soscw.com/index.php/essay/91455.html

亲，登录后才可以留言！

BZOJ 1029: [JSOI2007]建筑抢修（贪心）

评论

热门文章

推荐文章

最新文章

置顶文章