题意
有样物品,对于第个物品,你需要买个,每个物品在非打折日买是2块钱,在打折日买是1块钱。每天你可以赚1块钱。一共有个打折日,在第天第种物品打折,最少需要多少天可以买完你需要的物品
做法:二分
思路
- sale[]表示在允许天数内最晚打折时间 buy[]表示当前购买该物品的数量
- 二分天数,判断这些天数里能否买完所有物品
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=200010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); int n,m; ll k[N]; struct node{ int d,t; }a[N]; bool cmp(node x,node y){ return x.d<y.d; } int sale[N],buy[N]; bool check(ll mid){ ll day=0,money=0; rep(i,1,n) sale[i]=buy[i]=0; rep(i,1,m){ if(a[i].d<=mid) sale[a[i].t]=a[i].d; } rep(i,1,m){ if(a[i].d>mid) break; if(a[i].d>day) money+=a[i].d-day,day=a[i].d; if(sale[a[i].t]==a[i].d){ int cnt=min(money,k[a[i].t]-buy[a[i].t]); buy[a[i].t]+=cnt; money-=cnt; } } if(day<mid) money+=mid-day; rep(i,1,n){ if(buy[i]<k[i]) money-=2*(k[i]-buy[i]); } if(money<0) return 0; else return 1; } void solve(){ ll l=0,r=0,ans; cin>>n>>m; rep(i,1,n) cin>>k[i],r+=2*k[i]; rep(i,1,m) cin>>a[i].d>>a[i].t; sort(a+1,a+1+m,cmp); while(l<=r){ ll mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }