http://poj.org/problem?id=3040

从<=C的大面额开始凑钱,直到不小于C,然后看看这一次的凑钱凑了多少周。
重复上述操作直到不能凑钱。

/*0ms,200KB*/

const int mx = 25;

p2 a[mx];
int usecnt[mx];

int main()
{
    int n, c, i, ans = 0, rest, minweek;
    SII(n, c);
    For(i, n) SII(a[i].x, a[i].y);
    sort(a, a + n);
    while (true)
    {
        mem(usecnt, 0);
        rest = c;
        rFor(i, n - 1) /// 贪心:从大面额开始凑钱
     {
            usecnt[i] = min(a[i].y, rest / a[i].x);
            rest -= usecnt[i] * a[i].x;
        }
        if (rest)
        {
            For(i, n)
                if (a[i].y && a[i].x >= rest) /// 贪心:找一个小面额的补齐
                {
                    ++usecnt[i];
                    break;
                }
            if (i == n) break;
        }
        minweek = inf;
        /// 当C=12,且有1和5这样的面额时,会出现一次凑了两周的钱的情况
     For(i, n) if (usecnt[i]) minweek = min(minweek, a[i].y / usecnt[i]);
        ans += minweek;
        For(i, n) if (usecnt[i]) a[i].y -= usecnt[i] * minweek;
    }
    PI(ans);
    return 0;
}

Comments

comments powered by Disqus