首页 > 代码库 > Mixing Milk
Mixing Milk
链接
分析:水题,按照价格从小到大排序,在进行贪心即可
/* PROB:milk ID:wanghan LANG:C++ */ #include "iostream" #include "cstdio" #include "cstring" #include "string" #include "algorithm" using namespace std; const int maxn= 5000+10; struct Node{ int p,a; }; Node h[maxn]; bool cmp(Node x,Node y){ if(x.p==y.p) return x.a>y.a; return x.p<y.p; } int m; long long n; int main() { freopen("milk.in", "r", stdin); freopen("milk.out", "w", stdout); cin>>n>>m; for(int i=0;i<m;i++) cin>>h[i].p>>h[i].a; sort(h,h+m,cmp); long long ans=0; int flag=0; /*if(n>=h[0].a){ n-=h[0].a; ans+=(h[0].p*h[0].a); if(n==0) flag=1; }else{ flag=1; ans+=(h[0].a-n)*h[0].p; //n=-1; }*/ //cout<<ans<<endl; for(int i=0;i<m;i++){ if(flag) break; if(n>=h[i].a){ n-=h[i].a; ans+=(h[i].a*h[i].p); if(n==0) flag=1; }else{ ans+=n*h[i].p; n=-1; flag=1; } } cout<<ans<<endl; }
Mixing Milk
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。