时间戳

首页 > 技术文章 > 洛谷 CF436E Cardboard Box（反悔贪心）

洛谷 CF436E Cardboard Box（反悔贪心）

yinyuqin 2020-11-05 23:02 原文

传送门

解题思路

 枚举星星数，每加一颗星星，有以下情况：

  1. 零星关卡变成一星
  2. 一星关卡变成两星
  3. 一个零星关卡变成两星，一个一星关卡变成零星
  4. 一个零星关卡变成两星，一个两星关卡变成一星

转化为优选队列就是：

  • q1：零星关卡到一星的代价
  • q2：零星关卡到二星的代价
  • q3：一星关卡从二星变成一星的代价
  • q4：一星关卡的到一星的代价
  • q5：二星关卡从二星到一星的代价

四种情况为：

  1. 小根堆q1堆顶
  2. 小根堆q3堆顶
  3. 小根堆q2堆顶 - 大根堆q4堆顶
  4. 小根堆q2堆顶 - 大根堆q5堆顶

然后分别维护这五个队列即可。

注意：取堆顶前要先判断堆是否为空，且每种情况的初始值一定要初始化一个很大的longlong（不能用初始化int的值）

AC代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<algorithm>
 6 using namespace std;
 7 const int maxn=300005;
 8 int n,w,vis[maxn][3];
 9 long long minw;
10 long long ans,ans1,ans2,ans3,ans4;
11 struct node{
12     long long t1,t2;
13 }a[maxn];
14 priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q1,q2,q3;
15 priority_queue<pair<long long,int> > q4,q5;
16 int main(){
17     cin>>n>>w;
18     for(int i=1;i<=n;i++){
19         scanf("%lld%lld",&a[i].t1,&a[i].t2);
20         q1.push(make_pair(a[i].t1,i));
21         q2.push(make_pair(a[i].t2,i));
22         vis[i][0]=1;
23     }
24     for(int i=1;i<=w;i++){
25         ans1=ans2=ans3=ans4=0x3f3f3f3f3f3f;
26         while(!q1.empty()&&!vis[q1.top().second][0]) q1.pop();
27         while(!q2.empty()&&!vis[q2.top().second][0]) q2.pop();
28         while(!q3.empty()&&!vis[q3.top().second][1]) q3.pop();
29         while(!q4.empty()&&!vis[q4.top().second][1]) q4.pop();
30         while(!q5.empty()&&!vis[q5.top().second][2]) q5.pop();
31         if(!q1.empty()) ans1=q1.top().first;
32         if(!q3.empty()) ans2=q3.top().first;
33         if(!q2.empty()&&!q4.empty()) ans3=q2.top().first-q4.top().first;
34         if(!q5.empty()&&!q2.empty()) ans4=q2.top().first-q5.top().first;
35         minw=min(min(ans1,ans2),min(ans3,ans4));
36         ans+=minw;
37         if(minw==ans1){
38             int id=q1.top().second;
39             q1.pop();
40             vis[id][0]=0;
41             vis[id][1]=1;
42             q3.push(make_pair(a[id].t2-a[id].t1,id));
43             q4.push(make_pair(a[id].t1,id));
44             continue;
45         }
46         if(minw==ans2){
47             int id=q3.top().second;
48             q3.pop();
49             vis[id][1]=0;
50             vis[id][2]=1;
51             q5.push(make_pair(a[id].t2-a[id].t1,id));
52             continue;
53         }
54         if(minw==ans3){
55             int id1=q2.top().second;
56             int id2=q4.top().second;
57             q2.pop();
58             q4.pop();
59             vis[id1][0]=0;
60             vis[id1][2]=1;
61             vis[id2][1]=0;
62             vis[id2][0]=1;
63             q5.push(make_pair(a[id1].t2-a[id1].t1,id1));
64             q1.push(make_pair(a[id2].t1,id2));
65             q2.push(make_pair(a[id2].t2,id2));
66             continue;
67         }
68         if(minw==ans4){
69             int id1=q2.top().second;
70             int id2=q5.top().second;
71             q2.pop();
72             q5.pop();
73             vis[id1][0]=0;
74             vis[id1][2]=1;
75             vis[id2][2]=0;
76             vis[id2][1]=1;
77             q5.push(make_pair(a[id1].t2-a[id1].t1,id1));
78             q3.push(make_pair(a[id2].t2-a[id2].t1,id2));
79             q4.push(make_pair(a[id2].t1,id2));
80             continue;
81         }
82     }
83     cout<<ans<<endl;
84     for(int i=1;i<=n;i++){
85         if(vis[i][0]) printf("0");
86         else if(vis[i][1]) printf("1");
87         else if(vis[i][2]) printf("2"); 
88     }
89     return 0;
90 }

 

推荐阅读