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->- pa->b;
}

int cmp2(const void* a, const void* b) {
    node
* pa = (node*)a;
    node
* pb = (node*)b;
    
return pa->- 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;
}


posted on 2010-05-15 11:24 Willing 阅读(555) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理