题解 P1208 【[USACO1.3]混合牛奶 Mixing Milk】

· · 题解

貌似大家都在用快排啊

其实选择排序就能过

本人亲测

就在这里

——————————————（切入正题）————————————————

思路：排序+贪心

其实一开始看到题目时以为是背包，没办法，我太蒟了

既然是计算最小花费，那么就肯定是优先选择单价最便宜的

（貌似这句话是废话）

那单价一样的怎么办？

答曰：优先选择提供牛奶最多的

why？

排序结束后，就按照单价从小到大的顺序直接模拟，如果把产量最多的放前面，更省时

直接放代码

#include<bits/stdc++.h>//万能头（不过楼下好像不推荐）
using namespace std;

long long m,n;
long long p[5001],a[5001];
long long t,tt;
long long sum,ans;
//其实完全没有必要开long long，开了还占内存，但是在内存足够的情况下，更保险

int main()
{
    cin>>m>>n;
    //scanf("%lld%lld",&m,&n);
    //但是用cin也不会超时
    if(m==0)
    {
        cout<<"0"<<endl;
        return 0;
    }
    //这个特判一定要！如果需求为零，干嘛要买
    //我就被坑过QAQ
    for(int i=1;i<=n;i++)cin>>p[i]>>a[i];
    for(int i=1;i<=n;i++)
    {
        t=i;
        for(int j=i+1;j<=n;j++)
        {
            if(p[t]>p[j])t=j;
            if(p[t]==p[j])
            {
                if(a[t]<a[j])t=j;
            }
        }
        if(t!=i)
        {
            tt=p[i];p[i]=p[t];p[t]=tt;
            tt=a[i];a[i]=a[t];a[t]=tt;
        }
    }
    //以上是选择排序
    for(int i=1;i<=n;i++)
    {
        if(sum+a[i]<m)
        {
            sum+=a[i];
            ans=ans+a[i]*p[i];
            //如果买这个还不够的话，全部买掉继续往下找
        }
          else
          {
            ans=ans+(m-sum)*p[i];
            cout<<ans<<endl;
            return 0;
            //如果够了，只买自己需要的
            //再完美的结束程序
          }
    }
}