首页 > 代码库 > Codeforces Round #415 (Div. 2) B. Summer sell-off（贪心+结构体排序）
Codeforces Round #415 (Div. 2) B. Summer sell-off（贪心+结构体排序）
题目链接：http://codeforces.com/contest/810/problem/B
题意：给定天数和货物可以翻倍的天数，每天都有一定的货物量和顾客数，问怎么样货物才能卖得最多（前一天的货物不会留到下一天，每个顾客只能买一个货物）。
简单的贪心问题，贪心策略是：如果两倍的货物量卖出去的更多，就选两倍的，否则就选一倍的。
那一天能卖出去的货物量：min（货物量，顾客数）。然后根据结构体排序一下就ok了
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int N=1e5+10; 6 7 struct TnT{ 8 long long k; 9 long long l;10 }T[N];11 12 bool cmp(TnT a,TnT b){13 return (min(2*a.k,a.l)-min(a.k,a.l))>(min(2*b.k,b.l)-min(b.k,b.l));14 }15 16 int main(){17 long long n,f,res=0;18 cin>>n>>f;19 for(int i=0;i<n;i++){20 cin>>T[i].k>>T[i].l;21 }22 sort(T,T+n,cmp);23 for(int i=0;i<n;i++){24 if(f>0) {res+=min(2*T[i].k,T[i].l);f--;}25 else res+=min(T[i].k,T[i].l);26 }27 cout<<res<<endl;28 return 0;29 }
Codeforces Round #415 (Div. 2) B. Summer sell-off（贪心+结构体排序）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。