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!


#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, 0, sizeof(flag));
        int left = 0;
        for(int i=1; i<=n; ++i){
            scanf("%d", &x[i]);
            num[i] = x[i]*m/y;
            left += num[i];
            if( x[i]%y == 0 )  flag[i] = true;
        }
         left = m - left;
        while(left > 0){
            double tmp = 0.0;
            int p = 0;
            for(int i=1; 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[1]);
        for(int i=2; i<=n; ++i)
            printf(" %d", num[i]);
        printf("\n");
    }
    return 0;
}


目录
相关文章
|
6月前
|
算法
并查集,真好用,一次AC不是梦
并查集,真好用,一次AC不是梦
|
12月前
hdu 1052 Tian Ji -- The Horse Racing【田忌赛马】(贪心)
hdu 1052 Tian Ji -- The Horse Racing【田忌赛马】(贪心)
49 0
P2852 [USACO06DEC]牛奶模式Milk Patterns 后缀数组(poj3261)
P2852 [USACO06DEC]牛奶模式Milk Patterns 后缀数组(poj3261)
96 0
AC牛客 BM97 旋转数组
AC牛客 BM97 旋转数组
85 0
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
|
算法
HDU-1050,Moving Tables(不用贪心也AC)
HDU-1050,Moving Tables(不用贪心也AC)
HDU-1009,FatMouse' Trade(贪心水题)
HDU-1009,FatMouse' Trade(贪心水题)
UVa 11292 - Dragon of Loowater(排序贪心)
UVa 11292 - Dragon of Loowater(排序贪心)
95 0
|
存储
Weekly Contest 107 AC思路
Weekly Contest 107 AC思路
1373 0