题解：AT_agc034_c [AGC034C] Tests

· · 题解

\text{Solution}

看题解区都是二分的方法，这样的复杂度是 O(n\log V) 的，这里提供一种 O(n\log n) 的，时间复杂度在于排序。

考虑贪心，首先，假设已知最终高桥君的每科分数，那么对于分数比青木君大的场，c_i\gets r_i，否则 c_i\gets l_i。这是显然的。然后容易发现不存在 i,j，使得 a_i\neq 0,a_i\neq X 且 a_j\neq 0,a_j\neq X。

显然若存在这样的 i,j，一定可以将 c 值小的一个的分数给到，c 值大的一个。

那么有了这个性质，我们就可以先计算初始状态下青木君的总得分 sum，即 \sum\limits_{i=1}^{i=n}l_ib_i，那么考虑高桥君将 i 场考试学到 X 分的贡献，首先会抵消掉青木君的贡献，然后在 a_i>b_i 时，将 c_i 改为 r_i，则总贡献 w_i 为 l_ib_i+r_i(X-b_i)，将序列以这个值为关键字排序排序，可以求出一个最小的 i 使得 \sum\limits_{j=1}^{i}w_j \geq sum，分两种情况讨论：

1.若唯一的不为 0 且不为 X 的位置 j 是 [i,n] 中的，那么记 res\gets sum-\sum\limits_{k=1}^{i-1}w_k。先判断能否在 b_j 个以内完成超越，即 l_jb_j\geq res，此时答案为 \lceil \frac{res}{l_j}\rceil，否则答案为 b_j+\lceil \frac{res-l_jb_j}{l_j}\rceil。

2.若唯一的不为 0 且不为 X 的位置 j 是 [1,i) 中的，得先去除掉该位置的贡献并补上 i 位置的贡献，即 res\gets sum-(\sum\limits_{k=1}^{i-1}w_k-w_j+w_i)，剩下的过程与第一种情况一样。

/*
    Luogu name: Symbolize
    Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=2e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int n,x;
struct node
{
    int b;
    int l,r;
    int w;
}a[N];
bool cmp(node a,node b){return a.w>b.w;}
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
signed main() 
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();
    x=read();
    int sum=0;
    rep1(i,1,n)
    {
        a[i].b=read();
        a[i].l=read();
        a[i].r=read();
        a[i].w=(x-a[i].b)*a[i].r+a[i].b*a[i].l;
        sum+=a[i].b*a[i].l;
    }
    sort(a+1,a+n+1,cmp);
    rep1(i,1,n)
    {
        if(sum-a[i].w<=0)
        {
            int ans=inf;
            rep1(j,i,n) 
            {
                if(sum-a[j].b*a[j].l<=0) ans=min(ans,(sum+a[j].l-1)/a[j].l);
                else ans=min(ans,a[j].b+(sum-a[j].b*a[j].l+a[j].r-1)/a[j].r);
            }
            rep1(j,1,i-1)
            {
                int now=sum+a[j].w-a[i].w;
                if(now-a[i].w<=0) 
                {
                    if(now-a[j].b*a[j].l<=0) ans=min(ans,(now+a[j].l-1)/a[j].l);
                    else ans=min(ans,a[j].b+(now-a[j].b*a[j].l+a[j].r-1)/a[j].r);
                }
            }
            cout<<(i-1)*x+ans<<"\n";
            return 0;
        }
        sum-=a[i].w;
    }
    return 0;
}