1348 题解
所以我就来了,第一次在AcWing提交题解,还请多多包涵
Part 1 题目分析
这道题是个一眼题一眼dp, 然鹅冷静一下可是发现,贪心也可以做。
这里不给出证明了,主要就是讲个思路。
贪心的方法:
就是从单价最小的选到最大的。
如果要是当前需求量>相应奶牛可以提供的最大量。那么,我们就要全部选择,即最后的答案加上单位价格✖可提供的做大量,然后n减去可以提供的最大量即可。
反之,则最后的答案加上n✖单位价格,然后跳出循环即可。
这里为了保证代码简洁减少代码量,我们采用STL pair来实现。
Part 2 代码
//made by summerwhale
//any questions please email me or just text me on AcWing
//if wanna show anyone,please put my name on this code
//thanks! now enjoy it
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=10000010;
pair<int , int>a[N]; // first 表示单位价格 second 表示最大量
int ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i].first>>a[i].second;
}
sort(a+1,a+1+m);//从小到大排序
for(int i=1;i<=m;i++)
{
if(n>=a[i].second) //全部
{
ans+=a[i].first*a[i].second;
n-=a[i].second;
}
else//部分
{
ans+=n*a[i].first;
break;//结束循环
}
//cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}