训练赛第二场G题 ZOJ 2343
2024-09-01 07:36:26
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2343
解题报告:首先我假设最后的正确的结果是a[1] , a[2] ,a[3] ....a[i];然后我们先把这M个金币完全按照x[i] / Y的比例先预分配一下,分配的同时,统计出分配结束后还会剩余多少个金币,假设第一轮分配之后每个人得到的金币数量分别是k[1],k[2],......k[i],那么可以确定的是
a[i] - k[i] 是等于0或者等于1的,也就是说如果有些人的当前拿到的金币数量并不是符合最后的结果的话,那么这个人当前拿到的金币最多只比他应该得到的金币的数量少了一个,于是我们现在就可以将剩余的这left个金币分配给所有还少拿了一个金币的人,那么到底应该分给谁呢?
很显然,应该分给那个x[i]/Y - k[i]/M最大 的人,因为当分给这个人之后这个人的x[i]/Y - k[i]/M的值一定会变小,这样就可以达到总的值最小的目的。
#include<cstdio>
double Y,x[];
int N,M,k[]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%lf",&N,&M,&Y);
for(int i = ;i < N ;++i)
scanf("%lf",&x[i]);
int left = M;
for(int i = ;i<N;++i)
{
k[i] = 1.0 * ( x[i] / Y ) * M;
left -= k[i];
}
while(left)
{
int l = ;
for(int i = ;i < N;++i)
if(1.0*(double)x[i]/Y-(double)k[i]/(double)M >= 1.0*(double)x[l]/Y-(double)k[l]/(double)M)
l = i;
k[l]++;
left--;
}
for(int i = ;i < N;++i)
printf(i == ? "%d":" %d",k[i]);
puts("");
}
return ;
}
最新文章
- Picard报错“MAPQ should be 0 for unmapped read”的解决方法
- XML解析工具类
- 安卓第九天笔记-Activity
- ASP.NET 数据库访问通用工具
- 【leetcode】Intersection of Two Linked Lists(easy)
- [AngularJS] Design Pattern: Simple Mediator
- Linux - How To Set Up an NFS Mount on CentOS 6
- 浅谈 qmake 之 shadow build(将源码路径和构建路径分开,一套源码要分别用msvc2008、msvc2008、mingw分别编译又不互相干扰)
- C++ 函数映射使用讲解
- UIImageView 的contentMode属性 浅析
- linux权限---【600,644,700,755,711,666,777】 - - 博客频道 - CSDN.NET
- javascript-声明对象及其属性和方法
- 0x80070522:客户端没有所需的特权的解决方法(win7,win10通过)
- 【机器学习】K均值算法(I)
- 电脑kail linux 连接手机Nethunter,手机和电脑互传文件
- MySQL空间索引简单使用
- idea创建maven项目报错,Error initializing: org.codehaus.plexus.velocity.DefaultVelocityComponent@56da52a7 java.lang.NoClassDefFoundError: org/apache/commons/lang/StringUtils
- iOS中self.xxx 和 _xxx 下划线的区别
- 制作MACOSX10.10.3/10.9安装启动盘U盘的教程
- 教你轻松自己定义ViewPagerIndicator
热门文章
- exFAT移动硬盘写保护怎么去掉
- [转帖]七牛云对HTTPS 的解释
- google 浏览器插件安装
- BZOJ 2143 飞飞侠(分层最短路)
- HIGH-SPEED PACKET PROCESSING USING RECONFIGURABLE COMPUTING
- UOJ #7 【NOI2014】 购票
- 响应式开发(五)-----Bootstrap CSS----------Bootstrap 网格系统
- SSM 小demo的盲点总结
- 解题:USACO18FEB Taming the Herd
- bzoj 2300 : [HAOI2011]防线修建