贪心。按照每加仑的单价从小到大排序,这样才能保证花更少的钱买更多的牛奶。然后暴力就可以了。。

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7f7f7f7f;
struct T
{
    int p,a;
}s[5010];
bool cmp(T x,T y)
{
    return x.p<y.p;
}
int main()
{
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d%d",&s[i].p,&s[i].a);
    sort(s,s+m,cmp);
    int sum=0;
    for(i=0;i<m;i++)
    {
        if(n-s[i].a<0)
        {
            sum+=n*s[i].p;
            break;
        }
        else
        {
            n-=s[i].a;
            sum+=s[i].a*s[i].p;
        }
    }
    printf("%d\n",sum);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation