一个贪心贪不清楚的题目

2023-09-25 6 0

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);
}
代码编程
赞赏

相关文章

在用form 提交请求时,在请求处理完成后想要在JAVA后台设置返回信息状态展示到页面
深入探讨 Java 类加载器(转)
转载到QQ空间的js实现
web项目中参数传递乱码解决方法
tomcat 类加载时找不到class类文件
CRT工具远程Linux系统服务器的 命令