一道比较细节的贪心题
题意：
一个人可以选择在上午上班或者是在下午上班，不上班的时间可以摸鱼游玩
有n个室内的风景，m个室外的风景，这n+m个风景有一个漂亮值
对于这n+m个风景，如果第一次观看漂亮值转换为开心值比率为100%，如果重复观看，每重复一次就会变成之前的60%
对于室外的风景，下午观看会降到80%，上午观看不影响，如果在下午重复观看室外的风景，获得的开心值就是preVal * 80% * 60 %。（效果加成作用）
问这个人至少在白天工作k天( >= k)，总共n天，最大能获得多少开心值
输入：
2 1 4 2 4 3 7
输出：
18.20
样例解释：
上午7上午7*0.6下午4下午3
7 + 7 * 0.6 + 4 + 3 == 18.20
很容易想到用优先队列维护两块（室内室外）的风景，每当观看过之后，就对这个值*0.6，因为已经观看过了
然后要在白天工作至少k天，所以也就意味着至少要在下午观赏k天
先来一份Wa的赛事代码，队友实现的非常OK，但是在我们讨论过程中还是细节没有考虑好
#include<bits/stdc++.h> using namespace std; const int N = 100010; priority_queue<double,vector<double>,less<double> >q1;//室内 priority_queue<double,vector<double>,less<double> >q2;//室外 int main() { int n,m,k,t; cin >> n >> m >> t >> k; for(int i=1;i<=n;i++) { double x; cin >> x; q1.push(x); } for(int i = 1;i <= m;i++) { double x; cin >> x; q2.push(x); } k = t - k; double ans = 0; for(int i = 1;i <= k;i++) { double x = q1.top();q1.pop(); double y = q2.top();q2.pop(); if(x >= y) { ans += x; x *= 0.6; } else{ ans += y; y *= 0.6; } q1.push(x); q2.push(y); } k = t - k; for(int i = 1;i <= n;i++) { double x = q1.top();q1.pop(); double y = q2.top();q2.pop(); if(x >= y * 0.8){ ans += x; x *= 0.6; } else{ ans += y * 0.8; y *= 0.6; } q1.push(x); q2.push(y); } printf("%.2lf",ans); return 0; }
这份代码错就错在，将两部分进行分开考虑，实际上是不应该进行分开考虑的
也就是说：
所以最终Code就很容易啦:
int n,m,t,k; priority_queue<double> quea,queb; int main() { cin >> n >> m >> t >> k; for(int i=1; i<=n; i++) { double t; cin >> t; quea.push(t); } for(int i=1; i<=m; i++) { double t; cin >> t; queb.push(t); } double ans = 0; k = t-k; for(int i=1;i<=t;i++){ double topa = quea.top(); double topb = queb.top(); double mul = 1.0; if(k <= 0) mul = 0.8;///afternoon if(topa > topb * mul){ ans += topa; quea.pop();quea.push(topa * 0.6); }else{ ans += topb * mul; queb.pop();queb.push(topb * 0.6); k --; } } printf("%.2lf\n",ans); return 0; }//ac_code
![1275: [蓝桥杯2015决赛]五星填数](https://ucc.alicdn.com/pic/developer-ecology/5c72d809ed5c4e6495bdcef0433c87da.png?x-oss-process=image/resize,h_160,m_lfit)