D. PriceFixed

D. PriceFixed

题目连接🔗

题目大意
商店有n件商品，第i件商品，你需要买a[i]件，而第i件商品打折的够满b[i]件，问你怎样才能花最少的钱购买

思路
要求数少的，打折肯容易，要求数大的肯定难打折，那么贪心的去选取，先对需求非递减排个序，然后枚举如果当前的购买数满足打折条件那么就贪心买当前的商品，否则就拿后面的商品和当前的还需多少件商品数，取min，然后修改后面的值，这样能得到最优解

代码

#include 
using namespace std;
#define ll long long
#define fi first
#define se secondstruct node{ll req,lim;	bool operator <(const node &a)const{return lim<a.lim;}}a[200010];int main(){int n;ll sum=0;std::cin>>n;for(int i=1;i<=n;i++){std::cin>>a[i].req>>a[i].lim;}    sort(a+1,a+n+1);ll cnt=0,l=1,r=n;while(l<=r){if(a[l].lim<=cnt){cnt+=a[l].req;sum+=a[l].req;l++;}else {ll mm = min(a[r].req,a[l].lim-cnt);cnt+=mm;sum+=2*mm;a[r].req-=mm;if(a[r].req==0)r--;}}	std::cout<<sum;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！