浮世笑百姿

题目背景

跟着我说，“三二一，一二三，啊啊——”，快一点。

题目描述

兼具智慧与美貌的八重神子大人要来啦！旅行者要提前准备材料了。

旅行者需要准备 $n$ 种材料，第 $i$ 种材料需要 $a_i$ 份。为了获取材料，可以刷对应的副本（不同的材料需要刷不同的副本），每刷一次副本消耗一个树脂并有 $50\%$ 的概率获得一份该材料，为了方便，认为获得了半份材料。一开始旅行者有 $s$ 个树脂，同时每天可以获得 $1$ 个树脂（可以无上限地储存）。这些副本会不定期"up"，处于"up"状态的副本产出率会变成原来的 $2$ 倍。

无所不能的你提前知道了所有副本"up"的时间，共有 $m$ 条"up"信息，每条信息都形如第 $x$ 种材料对应的副本将在第 $t$ 天"up"。现在请你回答最快可以在第几天完成所有材料的准备工作。

输入格式

第一行三个整数 $n,m,s$，分别表示有 $n$ 种材料需要准备，有 $m$ 条”up“信息，初始有 $s$ 个树脂。

第二行 $n$ 个正整数 $a_i$，表示第 $i$ 种材料需要 $a_i$ 份。

接下来的 $m$ 行，其中第 $i$ 行两个正整数 $x_i,t_i$ ，表示第 $x_i$ 种材料对应的副本将在第 $t_i$ 天"up"。

输出格式

一行一个整数，表示完成所有材料的准备工作的最少天数。

样例 #1

样例输入 #1

5 2 7
1 3 4 4 2
2 4
4 4

样例输出 #1

14

提示

样例解释

第 $4$ 天有 $11$ 个树脂，刷 $3$ 次第 $2$ 种材料对应的副本，刷 $4$ 次第 $4$ 种材料对应的副本；

第 $14$ 天有 $14$ 个树脂，刷 $2$ 次第 $1$ 种材料对应的副本，刷 $8$ 次第 $3$ 种材料对应的副本，刷 $4$ 次第 $5$ 种材料对应的副本。

数据范围

对于所有的数据，满足 $1\leq n,s\leq 10^5$，$\sum a_i\leq 10^6$，$0\leq m\leq 10^5$，$1\leq x_i\leq n$，$1\leq t_i\leq 10^7$。

Subtask #1（30 points）：$1\leq n\leq 10^3$，$m=0$。

Subtask #2（20 points）：$1\leq n\leq 10^3$，$0\leq m\leq 10^3$。

Subtask #3（30 points）：保证每种副本最多只"up"一次。

Subtask #4（20 points）：无特殊限制。

Solution

贪心、二分

"up"是在当天将刷一次副本产出的材料数量从 $0.5$ 变成 $1$，不是使一个副本的产出变成之前的 $2$ 倍。

时间越长则获取的树脂越多，可能存在 up 的天数越多，故而答案存在单调性，考虑二分答案。由于每天可以刷无限次副本，时间越晚刷副本时可用的树脂越多，贪心选择时间范围内最晚 up 的一天刷对应材料。

为方便计算，认为每次刷副本可以获得一份材料，将需要的材料数量翻一倍。需要的材料数量 $a_i$ 为奇数时则不应在 up 时刷完，而是留 $1$ 份材料到最后。如果选择使用一份树脂刷出 $2$ 个材料就可能在处理其他材料时由于树脂不足而得到劣解，是错误的。

最后结算时处理所有未刷完的材料，总体时间复杂度 $O(n \log \sum a_i)$。

#include<bits/stdc++.h>
using namespace std;
struct Up{int i,t;}s[100005];
int n,m,k,ans,a[100005],las[100005],res[100005];
bool fail(int x){
    int day=0,sum=k;
    fill(las+1,las+n+1,0);
    copy(a+1,a+n+1,res+1);
    for(int i=1;i<=m;i++) if(s[i].t<=x) las[s[i].i]=i;
    for(int i=1;i<=m;i++) if(las[s[i].i]==i){
        sum+=s[i].t-day,day=s[i].t;
        int ned=min(sum,res[s[i].i]/2);
        sum-=ned,res[s[i].i]-=ned*2;
    }
    sum+=x-day;
    for(int i=1;i<=n;i++) if(res[i]){
        int ned=min(sum,res[i]);
        sum-=ned,res[i]-=ned;
    }
    for(int i=1;i<=n;i++) if(res[i]) return 1;
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]*=2;
    for(int i=1;i<=m;i++) cin>>s[i].i>>s[i].t;
    sort(s+1,s+m+1,[](auto x,auto y){return x.t<y.t;});
    int l=0,r=2'000'000;
    while(l<=r){
        int mid=(l+r)>>1;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    cout<<ans<<'\n';
    return 0;
}