Codeforces 1165F Microtransactions
题目链接
https://codeforces.com/contest/1165/problem/F2
题目大意
你需要购买 $n$ 个物品，每个需要购买 $k_i$ 个。你每天会获得 $1 \ burle$，每个物品价值 $2 \ burles$，有 $m$ 个促销活动，其中 $d_i$ 天 $t_i$ 物品价格会变成 $1 \ burle$，问最少多少天收集齐所有的物品。
题目分析
考虑如果问 $x$ 天时间，问是否可以买完所有需要的物品。从前往后扫描显然会出现钱不够不知道该买谁的情况，考虑从后往前扫描，那么每过一天获得的 $burle$ ，直接购买有必要购买的即可，因为前面节省下来的钱，后面肯定可以用。
解决了这个问题那么就很容易了，它已经具备了二分答案的先决条件了，直接二分即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, t;
int a[maxn];
int b[maxn];
struct ex {
int d, t;
};
vector <ex> vec;
bool cmp(ex x, ex y){
return x.d > y.d;
}
int read(){
int x;
scanf("%d", &x);
return x;
}
bool check(int x){
int i, j = 0;
int cnt = 0, sum = 0;
queue <ex> q;
for(i=1;i<=n;i++){
b[i] = a[i];
sum += b[i];
}
for(ex tmp : vec){
if(tmp.d > x)continue;
q.push(tmp);
}
for(i=x;i>0;i--){
while(q.size() and !b[q.front().t])q.pop();
if(q.size() and q.front().d >= i){
b[q.front().t]--;
cnt++;
}
}
return x - cnt >= 2 * (sum - cnt);
}
int main(){
int i, j;
int x, y;
int l = 0, r;
n = read();
m = read();
for(i=1;i<=n;i++){
a[i] = read();
l += a[i];
}
for(i=1;i<=m;i++){
x = read();
y = read();
vec.push_back({x, y});
}
sort(vec.begin(), vec.end(), cmp);
r = 2 * l;
while(l < r){
int mid = (l + r) / 2;
if(!check(mid)){
l = mid + 1;
}else{
r = mid;
}
}
printf("%d\n", l);
return 0;
}