http://acm.sgu.ru/problem.php?contest=0&problem=207
大致翻译:n个强盗去抢劫银行得到m个金币,抢劫前他们先确定好了分配方案,每个人按比例Xi/Y分配,X1+X2+..Xn = Y,m可能不能被Y整除,所以实际分配可能会有不公平,假设第i个强盗分配到Ki个金币,定义不公平度为|Xi/Y-Ki/m|,给出了n,m,Y,Xi,求出Ki,使得不公平度的总和最小
首先不公平度乘以Y*m不会影响结果,得到Xi*m - Y*Ki。则Ki必定取值[Xi*m/Y]或[Xi*m/Y]+1(怎样证明我也不知道。。感觉是这样。)
那么可以先让每个强盗先分到[Xi*m/Y]个金币,然后再按不公平度的大小排序(最大的排前面),让排在前面的强盗分别得到1个金币(直到金币分完)
其实就是贪心了,每次让强盗再得到1个金币都让不公平度最大程度地减小。
#include <stdio.h>
#include <stdlib.h>
typedef struct tagNode {
int k;
int b;
int i;
} node;
int cmp1(const void* a, const void* b) {
node* pa = (node*)a;
node* pb = (node*)b;
return pb->b - pa->b;
}
int cmp2(const void* a, const void* b) {
node* pa = (node*)a;
node* pb = (node*)b;
return pa->i - pb->i;
}
int main(void) {
int n, m, y;
scanf ("%d%d%d", &n, &m, &y);
int x[1000];
node h[1000];
int i, total = m;
for (i = 0; i < n; ++i) {
scanf ("%d", x+i);
h[i].k = m*x[i]/y;
h[i].b = m*x[i]%y;
h[i].i = i;
total -= h[i].k;
}
qsort(h, n, sizeof(h[0]), cmp1);
i = 0;
while (total--) {
h[i++].k++;
}
qsort(h, n, sizeof(h[0]), cmp2);
printf ("%d", h[0].k);
for (i = 1; i < n; ++i) {
printf (" %d", h[i].k);
}
printf ("\n");
return 0;
}