51Nod－1246－罐子和硬币

ACM模版

描述

题解

这里需要强调的是，分配是我们决定的，拿的方案也是我们决定的，所以，这里默认是我们知道每个罐子可能拥有的硬币个数。一开始没有读懂这层隐藏条件，所以自己想了半天也没有想通样例……

接着，我们需要考虑的是两大种情况四小种情况：
第一：无抓空情况，结果一定是c次。
1、每个罐子的硬币个数我们都知道（一定是每个罐子硬币个数都是一样的）。
2、分配方案最优时（尽量均分），硬币个数最少的个数x*罐子数n大于等于要取的个数。
第二：有抓空情况，结果一定是两种（c + y 、 res）子情况中最优的一种。
3、根据尽量均分原则，我们可以分析到每个罐子要么是x个，要么是x+1个，如果此时x个的罐子小于x+1个的罐子数目，那么结果一定是未抓空的c次加上最多抓空的次数y。
4、但是当x个的罐子少于x+1个的罐子时，我们是否可以考虑，保证尽量多的罐子为x+1状态，那么最多抓空的次数z一定是未满x+1个的罐子数，res一定是未抓空的次数c加上最多抓空的次数z。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{
    int n, k, c;

    while (cin >> n >> k >> c)
    {
        // 这道题要说的就是，分配是我们自己分配
        // 拿的时候也是我们自己拿的，所以，
        // 我们是可以知道每个罐子中可能有几个的

        // 想要最糟询问方案次数最少，需要先考虑
        // 不会出现抓空的情况(尽量均分) (1)
        // 其次要考虑尽量少抓空的情况 (2)
        int x = k / n;      // 每个罐子最少x个
        int y = n - k % n;  // y个罐子有x个，其他的罐子有x+1个

        if (x * n >= c || k % n == 0)   // (1)
        {
            // 当出现这两种情况时，我们一定不会浪费询问次数的
            printf("%d\n", c);
        }
        else                            // (2)
        {
            // 两种情况 第一种是尽量均分策略: c+y(最糟糕抓空y次)
            // 第二种是保证足够多的罐子装x+1: res(最多抓空n-z次)
            int z = k / (x + 1);              // z个罐子可以方x+1个
            int res = n - z + c;              // 会抓空n-z次，然后有c次没有抓空
            printf("%d\n", min(res, c + y));  // 从两种情况中保留最少的次数并输出
        }
    }

    return 0;
}