传送门

我们先二分答案,这样就确定了优惠购买的个数和不优惠购买的个数,判断可行性即可。这时容易建出费用流模型,跟二分图最大权匹配类似,不过右边只有两个点,且右边的每个点可以匹配多个左边的点。

我们考虑怎么优化这个费用流,跟朴素的找最短增广路的费用流算法类似,我们也可以每次找一条权值最小的增广路进行增广。由于增广路的长度是$O(1)$的(因为如果不是$O(1)$的,增广路会经过右边的两个点中的其中一个至少两次,然而最短路费用流算法是不会在增广过程中产生负权回路的,这就意味着不可能重复经过一个点,这就矛盾了),所以我们可以用数据结构维护最优的增广路(分四种情况讨论)。

结果写完之后T了。。。想了想怎么1个log做,发现直接把二分答案去掉,从0开始枚举,每次在上一次跑的残量网络上直接把容量会改变的那条边的容量+1,然后接着找增广路就行了。由于改动的边费用是0,所以改完之后并不会产生负权回路,所以这个做法是正确的,复杂度变成了$O(n\log n)$。

#include <bits/stdc++.h>
#define MAXN 100010
#define LL long long
using namespace std;

int n,m,m1,m2;
int c1,c2;
LL lim,res;
pair<LL,LL> a[MAXN];
set< pair<LL,int> > S1,S2,S3,S4;

bool check(){
    pair<LL,int> t1=*S1.begin(),t2=*S2.begin(),t3=*S3.begin(),t4=*S4.begin();
    LL s1=t1.first; if(c1==m1) s1=1LL<<50;
    LL s2=t2.first; if(c2==m2) s2=1LL<<50;
    LL s3=t1.first+t3.first; if(c2==m2) s3=1LL<<50;
    LL s4=t2.first+t4.first; if(c1==m1) s4=1LL<<50;
    LL s=min(min(s1,s2),min(s3,s4));
    if(s1==s){
        int i=t1.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S3.insert(make_pair(a[i].second-a[i].first,i));
        c1++;
    }else if(s2==s){
        int i=t2.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S4.insert(make_pair(a[i].first-a[i].second,i));
        c2++;
    }else if(s3==s){
        int i=t1.second,j=t3.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S3.insert(make_pair(a[i].second-a[i].first,i));
        S3.erase(S3.find(make_pair(a[j].second-a[j].first,j)));
        S4.insert(make_pair(a[j].first-a[j].second,j));
        c2++;
    }else if(s4==s){
        int i=t2.second,j=t4.second;
        S1.erase(S1.find(make_pair(a[i].first,i)));
        S2.erase(S2.find(make_pair(a[i].second,i)));
        S4.insert(make_pair(a[i].first-a[i].second,i));
        S4.erase(S4.find(make_pair(a[j].first-a[j].second,j)));
        S3.insert(make_pair(a[j].second-a[j].first,j));
        c1++;
    }
    res+=s;
    return res<=lim;
}

int gao(){
    m1=m;
    m2=1;
    S3.insert(make_pair(1LL<<50,0));
    S4.insert(make_pair(1LL<<50,0));
    for(int i=1;i<=n;i++){
        S1.insert(make_pair(a[i].first,i));
        S2.insert(make_pair(a[i].second,i));
    }
    for(int i=1;i<=m;i++) check();
    while(check()) 
        m2++;
    return m1+m2-1;
}

int main(){
#ifdef DEBUG
    freopen("130.in","r",stdin);
#endif
    scanf("%d%d%lld",&n,&m,&lim);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].second,&a[i].first);
    sort(a+1,a+n+1);
    LL temp=0;
    for(int i=1;i<=m;i++){
        temp+=a[i].first;
        if(temp>lim){
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d\n",gao());
    return 0;
}