二分-贪心-费用流

EnofTaiPeople · 2022-04-15 10:30:53 · 题解

大赛之前照例是要写一篇黑题题解的，省选加油！

这道题空间限制小，但并不卡常，只是对于精准计算要求较高，时限超级充裕，毕竟我的代码最慢测试点也只用了不到一秒。

首先，对于第一问，因为如果 t 成立，那么 \forall t'>t 都成立，所以答案具有二分性。对于是否有解，可以贪心判断：在零时刻把所有股票换成 ta+b 最大的股票，在 t 时刻按需从大往小兑换，如果某一刻，手中的股票张数为负，就说明不行：

stl bool cmp2(const int &x,const int &y){
    ll tx=tt*a[x]+b[x],ty=tt*a[y]+b[y];
    return tx==ty?x>y:tx<ty;
}
stl bool cmp1(const int &x,const int &y){
    return b[x]==b[y]?x>y:b[x]<b[y];
}
stl bool ck(){
/*main(){
    stable_sort(p+1,p+n2+1,cmp1);
}*/
    int i,nw=0;
    for(i=1;i<=n2;++i)ct[i]=0;
    for(i=1;i<=n2;++i){
        if(cmp2(nw,p[i]))nw=p[i];
        if(p[i]<=n)++ct[nw];
    }stable_sort(q+1,q+n2+1,cmp2);
    for(i=n2,nw=0;i;--i){
        nw+=ct[q[i]];
        if(q[i]>n)if(!nw--)return 0;
    }return 1;
}

好了，第一问解决，第一问告诉我们，一张股票如果要换，只需要最多换两次，就能换到所有能换到的股票，但不一定需要两次，于是这成了一个简单的费用流模型，需要建四层图，为了不让边达到 O(n^2) 级别，我们可以采用前缀和优化，例如样例二所对应的图如下（只显示了容量）：

然后大胆地跑 \text{spfa} 就可以啦！由于边权极小，图无特殊性质，\text{spfa} 可以看作线性，所以总复杂度为 O(n\log_2n\log_2C+kn^2)，C 为值域，k 是一个较小的常数。