poj3040(双向贪心)

Allowance

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1540		Accepted: 637

Description

As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly
divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute
the maximum number of weeks he can pay Bessie.

Input

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John's possession.

Output

* Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance

Sample Input

Sample Output

Hint

INPUT DETAILS:

FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.

OUTPUT DETAILS:

FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.

Source

field=source&key=USACO+2005+October+Silver">USACO 2005 October Silver

题目得意思是，john要发硬币工资给他的奶牛。工资不低于c,他有n个硬币，币值和数目。

问你最多发多少个星期。

人云亦云啊，我也用双向贪心。哎。

从大到小排好序，从头到尾做一轮，再反过来做一轮。没有严谨证明，奇奇怪怪的感觉。

（可是我看到硬币就想到dp...）

/***********************************************************

	> OS     : Linux 3.13.0-24-generic (Mint-17)

	> Author : yaolong

	> Mail   : dengyaolong@yeah.net

	> Time   : 2014年10月14日 星期二 09时59分40秒

 **********************************************************/

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <algorithm>

using namespace std;

pair<int, int> a[25];

int use[25];

int n, m;

int main()

{

    while ( scanf ( "%d%d", &n, &m ) != EOF )

    {

        int i;

        for ( i = 1; i <= n; i++ )

        {

            scanf ( "%d%d", &a[i].first, &a[i].second );

        }

        sort ( a+1, a + n+1 );

        int res = 0;

        while ( 1 )

        {

            memset ( use, 0, sizeof ( use ) );

            int rest = m;

            for ( i = n; i >= 1; i-- )

            {

                int tmp = min ( rest / a[i].first, a[i].second );

                rest -= tmp * a[i].first;

                use[i] = tmp;

            }

            if ( rest )

            {

                for ( i = 1; i <= n; i++ )

                {

                    if ( a[i].second && a[i].first >= rest )

                    {

                        use[i]++;

                        rest = 0;

                        break;

                    }

                }

            }

            if ( rest )

            {

                break;

            }

            int mmin = 0x7f7f7f7f;

            for ( i = 1; i <= n; i++ )

            {

                if ( use[i] )

                {

                    mmin = min ( mmin, a[i].second / use[i] );

                }

            }

            res += mmin;

            for ( i = 1; i <= n; i++ )

            {

                if ( use[i] )

                {

                    a[i].second -= use[i] * mmin;

                }

            }

        }

        cout << res << endl;

    }

}

巴特西

poj3040(双向贪心)

最新文章

热门文章