Mr.Maxwell and attractions E起来编程暨第三届湖北省赛

B-Mr.Maxwell and attractions_“深圳计算科研院杯“E起来编程暨第三届湖北省赛 (nowcoder.com)

题意

有n个户外，m个户内活动，总共T天，至少K下午天去户外

第二次去同一个地点获得开心值为原本的0.6， 如果同时满足户外和下午，则开心值为原来0.6倍的基础上在乘0.8

问：开心值最大值为多少？

题解

贪心策略：室内的尽量放下午，室外的尽量放上午

但是当只能安排在下午了，要比较的是户内最大值 和 户外最大值*0.8

if(mor == 0) {flag = a >= 0.8 * b ? 1 : 0;}
else {flag = a >=  b ? 1 : 0;}

ps: 队友用的是优先队列，因为有效值为队头

我更喜欢multiset（顺手，而且multiset可以在中间取值，删值

but，multiset常数大，慢的很！

//看看下面，是队列时间的三倍

#include <bits/stdc++.h>
const int MAX = 1e5 + 10;
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;struct node {double a;bool operator<(const node &x) const {return a > x.a;}
};multiset<node> ans1, ans2;
double indo[MAX], outdo[MAX];int main() {int N, M, T, K;scanf("%d%d%d%d", &N, &M, &T, &K);for (int i = 0; i < N; i++) {scanf("%lf", &indo[i]);ans1.insert({indo[i]});}for (int i = 0; i < M; i++) {scanf("%lf", &outdo[i]);ans2.insert({outdo[i]});}double res = 0;int mor = T - K;int aft = K;while (1) {if (!mor && !aft) break;double a = ans1.begin()->a;double b = ans2.begin()->a;//室内的尽量放下午，室外的尽量放上午bool flag;if(mor == 0) {flag = a >= 0.8 * b ? 1 : 0;}else {flag = a >=  b ? 1 : 0;}if(flag) {res += a;ans1.erase(ans1.begin());ans1.insert({a * 0.6});if(aft >= 1) {aft--;}else if(mor >= 1){mor--;}else break;}else {if(mor >= 1) {mor--;res += b;ans2.erase(ans2.begin());ans2.insert({b * 0.6});}else {aft--;res += b * 0.8;ans2.erase(ans2.begin());ans2.insert({b * 0.6});}}}printf("%.2lf\n", res);
}