题号 NC113693
名称 Microtransactions (hard version)
来源 CF1165F2
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：喵渺淼妙的死忠粉
思路
=
二分答案,贪心验证.
我们二分出最少需要多少天可以做完.然后贪心的把所有做的,推到我们二分答案限度内的最后一天,不是在我二分答案外的最后一天.
不然类似下面的数据就过不去.

4 7
23 78 12 46
100 1
41 3
213 2
321 3
12 2
87 1
76 2

213

然后本题就做完了,还有在函数内不可以开vector<int>last[N],因为挺大的,所以跑不出,还是老老实实的清0吧.</int>

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,m,k[N],s[N];//每个物品需要的个数
vector<int>nm[N];//以及该物品可以最后买的时间. 
struct Ans{
    int d,t;
}a[N];
bool cmp(Ans A,Ans B)
{
    if(A.t==B.t)    return A.d>B.d;
    else            return A.t<B.t;
}
vector<int>last[N];
bool ck(int u)
{
    for(int i=1;i<=n;i++)    s[i]=k[i];
    for(int i=1;i<=u;i++)    last[i].clear();
    int num=0;
    //应该选取在u以内的最后面.
    for(int i=1;i<=n;i++)
    {
        int pos=0;
        for(int j:nm[i])
        {
            if(j>u)    break;
            pos=j;
        }if(pos)    last[pos].push_back(i);
    }
    for(int i=1;i<=u;i++)
    {
        num++;
        for(int j:last[i])
        {
            if(num>s[j])    num-=s[j],s[j]=0;
            else            s[j]-=num,num=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        num-=(s[i]<<1);
    }return num>=0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)    cin>>k[i];
    for(int i=1;i<=m;i++)    cin>>a[i].d>>a[i].t,nm[a[i].t].push_back(a[i].d);
    for(int i=1;i<=n;i++)    sort(nm[i].begin(),nm[i].end());
    int l=0,r=4e5,ans=2e9;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(ck(mid))
        {
            ans=min(ans,mid);
            r=mid-1;
        }
        else    l=mid+1;
    }cout<<ans<<'\n';    
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目3月1日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴