codeforces#1165 F2. Microtransactions (hard version) （二分+贪心）

题目链接：

https://codeforces.com/contest/1165/problem/F2

题意：

需要买$n$种物品，每种物品$k_i$个，每个物品需要两个硬币

每天获得一个硬币

有$m$个优惠

在$d_i$天，$t_i$物品卖一个硬币

求购买所需物品最少需要的天数

数据范围：

$1 \le n, m \le 2 \cdot 10^5$

分析：

我们可以注意到，如果某天是某个物品的最后优惠时间，那么我们一定要在这天尽可能多地购买这个物品

对答案进行二分

再二分得到每个物品在这个答案下的最后优惠时间

贪心购买每种物品

复杂度$O(lgn*lgn*n)$

ac代码：

#include<bits/stdc++.h>

#define ll long long

#define pa pair<int,int>

using namespace std;

const int maxn=2e5+10;

const ll mod=998244353;

vector<int>ve[maxn];

int sale[maxn*10],sum,num[maxn],n,m;

bool check(int day)//检查天数为day时，能不能买完所以需要的东西

{

    for(int i=1;i<=day;i++)sale[i]=0;//购买最后期限为i的物品数量

    for(int i=1;i<=n;i++)

    {

        if(ve[i].size()==0)continue;

        int st=0,en=(int)ve[i].size()-1;//二分每种物品的最后期限

        while(st!=en)

        {

            int md=(st+en)/2;

            if(ve[i][md+1]<=day)st=md+1;

            else en=md;

        }

        sale[ve[i][st]]+=num[i];

    }

    int money=0,buy=0;

    for(int i=1;i<=day;i++)//只要是最后期限，那么这个物品我们就买最多

    {

        money++;

        buy+=min(money,sale[i]);

        money-=min(money,sale[i]);

    }

    if(money>=2*(sum-buy))return 1;

    else return 0;

}

int main()

{

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&num[i]);

        sum+=num[i];

    }

    for(int i=1;i<=m;i++)

    {

        int a,b;

        scanf("%d %d",&a,&b);

        ve[b].push_back(a);

    }

    for(int i=1;i<=n;i++)

        sort(ve[i].begin(),ve[i].end());

    int st=sum,en=2*sum;//对答案二分

    while(st!=en)

    {

        int md=(st+en)/2;

        if(check(md))en=md;

        else st=md+1;

    }

    printf("%d\n",st);

    return 0;

}

巴特西

codeforces#1165 F2. Microtransactions (hard version) （二分+贪心）

题目链接：

题意：

数据范围：

分析：

ac代码：

最新文章

热门文章