HDOJ 2111 Saving HDU 解题报告 - Linux安全网 - Linux操作系统_Linux 命令_Linux教程

HDOJ 2111 Saving HDU 解题报告

日期:2011-07-26 点击:37 来源: 未知分享至:

http://acm.hdu.edu.cn/showproblem.php?pid=2111

还是贪心。。。。

Run ID	Submit Time	Judge Status	Pro.ID	Exe.Time	Exe.Memory	Code Len.	Language	Author
4252500	2011-07-25 16:00:53	Accepted	2111	0MS	296K	922 B	G++	GongZi

//HDOJ 2111 Code By NetBeans 6.9.1
#include <iostream>
#include <algorithm>

using namespace std;

struct A
{
    int p, m;
};

bool cmp( A x, A y );

int main()
{
    int v, n;
    while( cin >> v && v )
    {
        cin >> n;
        A treasure[n];
        for( int i = 0; i < n; ++i )
        {
            cin >> treasure[i].p >> treasure[i].m;
        }
        sort( treasure, treasure + n, cmp );
        int sum = 0;
        for( int i = 0; i < n && v > 0; ++i )
        {
            if( treasure[i].m >= v )
            {
                sum += treasure[i].p * v;
                v = 0;
            }
            else
            {
                sum += treasure[i].m * treasure[i].p;
                v -= treasure[i].m;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

bool cmp( A x, A y )
{
    return x.p > y.p;
}
#if gongzi
#endif

Tags：

分享至: