Codeforces Round #560 (Div. 3)F1.F2. Microtransactions (easy version)
题目来源:
F1:https://codeforces.com/contest/1165/problem/F1
F2:https://codeforces.com/contest/1165/problem/F2
题意:AA现在有n种装备要买,每个装备要买ki个,每一天的早上AA会赚到1元钱,每个装备的价钱都是2元,但是现在有m个特价活动(d1,ti)意思是在di天的时候第ti个装备只要1元钱,问你买完所有的装备所需的最小天数是多少?
F1 和 F2的题是一样的,只是数据范围不一样,我用的方法都是二分(logn的时间复杂度)所以两个题的代码是一样的,都可以过。
思路:
其实这个是一道二分题,和之前做的一个题晾衣服的题好像差不多,奈何我还是不太会最后为了假装ak过cf然后就py了网友代码,谁知道这一py直接就rank1了QAQ。
每张碟的价格都是一样的,那么普通价格的不管我在什么时候买都是一样的,所以可以默认全部都在最后一天买。在考虑打折的碟。如果某张碟子打了多次折,那么我可以留到最后一次打折再买。然后就可以二分了,check的时候从mid天往前倒着推,遇到打折的就直接买够,最后判断一下不打折的就可以了,这里像贪心。
参考代码:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define PB push_back
#define POP pop_back
#define FI first
#define SE second
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
const LL N=4e5+7,mod=998244353,INF=1e9;
int n,m;
int a[N],b[N];
vector<int>v[N];
int check(int x,int y){
int re=x,cnt=0;
int flag=0;
for(int i=1;i<=n;i++)b[i]=a[i];
for(int i=x;i>=1;i--){
//cout<<i<<' '<<re<<endl;
for(int j=0;j<v[i].size();j++){
while(b[v[i][j]]&&re){
re--;
y--;
b[v[i][j]]--;
}
}
if(re>=i)re--,flag++;
}
return flag/2>=y;
}
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt+=a[i];
}
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
v[x].PB(y);
}
int ans=INF;
int l=cnt,r=2*cnt;
while(l<=r){
int mid=l+r>>1;
if(check(mid,cnt)){
ans=min(ans,mid);
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<endl;
return 0;
}