[洛谷P1750]KC喝咖啡
2024-08-31 10:13:59
题目大意:给你n个物品,每个物品有一个价值$v_i$和一个时间$t_i$,要你取m个物品,使得他们的美味度($\frac{\sum v_i}{\sum t_i}$)最大,求这个美味度。
解题思路:由于$n\le 200$,我们可以贪心。我们用V和T记录当前的$v_i$之和和$t_i$之和,那么我们每次在能取的物品里,找一个能使$\frac{V+v_i}{T+t_i}$最大的物品i,把它取走,最后就能得到最优解。时间复杂度$O(nm)$。
C++ Code:
#include<cstdio>
using namespace std;
int n,m,t[202],v[202];
bool vis[202];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&v[i]);
for(int i=1;i<=n;++i)scanf("%d",&t[i]);
int V=0,T=0,now=0;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j)
if(!vis[j]&&(now==0||((double)(V+v[now])/(T+t[now])<(double)(V+v[j])/(T+t[j]))))now=j;
V+=v[now];
T+=t[now];
vis[now]=true;
now=0;
}
printf("%.3f\n",(double)V/T);
return 0;
}
最新文章
- VehicleCamera解读
- avalonjs
- python day2 列表的常用操作方法
- Docker ntpdate Permition error
- Eclipse主题更改
- Nginx php-fpm php mysql
- android 实现自定义卫星菜单
- How to change data dir of mysql?
- 跟我学机器视觉-HALCON学习例程中文详解-开关引脚测量
- ASP.NET MVC 5 学习教程:添加模型
- adb 命令使用的时候出现Error
- Caused by: java.lang.ClassNotFoundException: org.jboss.logging.BasicLogger
- js+jq实现图片预览,支持到ie9+ff+chrome
- socket网络编程-----I/O复用之poll函数
- 【Java】 剑指offer(10) 旋转数组的最小数字
- JavaScript深入系列15篇
- Error:java: invalid source release 无效的源发行版: 8
- eventql部署过程
- tensorflow笔记之滑动平均模型
- asp.net 中使用 pagedlist 分页并具有查询功能的实现方法