首页 > 代码库 > AC_Dream 1224 Robbers（贪心）
AC_Dream 1224 Robbers（贪心）
题意：n个抢劫犯分别抢到的金钱是k1, k2, k3,...，一共得到的金钱是m，
但是在分钱的时候是按照x1/y, x2/y, x3/y,....的比例进行分配的！这样的话
一些抢劫犯就会觉得不公平，不公平度为|xi/y - ki/m|(浮点运算)， 输出一个序列ki，使得
总的不公平度最小.....
思路：很明显的贪心！ 首先按照 [xi/y](取整)的比例将每一个人得到的钱求出来(ni)，然后会得到
剩下的钱数, 最后在所有人中找到谁分配的相对比例少了，也就是xi/y*m - ni的最大值！找到这个人
之后，将他得到的钱数加 1！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define N 1006 5 using namespace std; 6 7 int num[N]; 8 int x[N]; 9 bool flag[N];10 11 int main(){12 int n, m, y;13 while(scanf("%d%d%d", &n, &m, &y) != EOF){14 memset(flag, 0, sizeof(flag));15 int left = 0;16 for(int i=1; i<=n; ++i){17 scanf("%d", &x[i]);18 num[i] = x[i]*m/y;19 left += num[i];20 if( x[i]%y == 0 ) flag[i] = true;21 }22 left = m - left;23 while(left > 0){24 double tmp = 0.0;25 int p = 0;26 for(int i=1; i<=n; ++i)27 if(tmp < x[i]*1.0/y * m - num[i]){28 tmp = x[i]*1.0/y * m - num[i];29 p = i;30 } 31 --left;32 ++num[p];33 }34 printf("%d", num[1]);35 for(int i=2; i<=n; ++i)36 printf(" %d", num[i]);37 printf("\n");38 }39 return 0;40 }
AC_Dream 1224 Robbers（贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。