题意:n个抢劫犯分别抢到的金钱是k1, k2, k3,...,一共得到的金钱是m,
但是在分钱的时候是按照x1/y, x2/y, x3/y,....的比例进行分配的!这样的话
一些抢劫犯就会觉得不公平,不公平度为|xi/y - ki/m|(浮点运算), 输出一个序列ki,使得
总的不公平度最小.....
思路:很明显的贪心! 首先按照 [xi/y](取整)的比例将每一个人得到的钱求出来(ni),然后会得到
剩下的钱数, 最后在所有人中找到谁分配的相对比例少了,也就是xi/y*m - ni的最大值!找到这个人
之后,将他得到的钱数加 1!
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1006
using namespace std; int num[N];
int x[N];
bool flag[N]; int main(){
int n, m, y;
while(scanf("%d%d%d", &n, &m, &y) != EOF){
memset(flag, , sizeof(flag));
int left = ;
for(int i=; i<=n; ++i){
scanf("%d", &x[i]);
num[i] = x[i]*m/y;
left += num[i];
if( x[i]%y == ) flag[i] = true;
}
left = m - left;
while(left > ){
double tmp = 0.0;
int p = ;
for(int i=; i<=n; ++i)
if(tmp < x[i]*1.0/y * m - num[i]){
tmp = x[i]*1.0/y * m - num[i];
p = i;
}
--left;
++num[p];
}
printf("%d", num[]);
for(int i=; i<=n; ++i)
printf(" %d", num[i]);
printf("\n");
}
return ;
}