CF2275D Precision Alignment 题解

· · 题解

考虑如何区。

最小的最大显然考虑二分，二分可以达到的这个 \min 值 mid。

那么 check 的时候只需要处理每个三元组和提升到 \ge mid 所需的次数，加起来判断是否 \le k 即可。

因此问题转化为只需要知道对于一组 (a,b,c) 如何用最小的次数升到 a'+b'+c' \ge mid 了。

首先如果 a+b+c 已经达到 mid，次数为 0。

然后如果 a=b=c，永远也动不了，特判掉。

否则，只要存在 a>b 或 a>c 或 b>c，就一定可以通过 > 的那个二元组提升剩下一个值，因此次数为 mid-(a+b+c)。

如果无法直接提升就是 a \le b \le c。是否以为这样就动不了了？并非，可以尝试将 b 降低到 <a，或者将 c 降低到 <b，就转化为上一种情况。这个时候，除了基本次数 mid - (a+b+c) 以外，还额外有 2 \times \min(b-a+1,c-b+1) 的代价，因为你降下去了又得重新升回来。

那么就可以据此写 check 函数了。注意二分范围一定要开足。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL INF = 2e18+1099;
LL T,n,k,a[N],b[N],c[N],l,r,Ans;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
LL get__(int i,LL up){
    if(a[i]+b[i]+c[i]>=up)return 0;
    if(a[i]==b[i]&&b[i]==c[i])return -1;
    if(a[i]>b[i]||a[i]>c[i]||b[i]>c[i])
        return up-a[i]-b[i]-c[i];
    return up-a[i]-b[i]-c[i]+2*min(b[i]-a[i]+1,c[i]-b[i]+1);
}
bool check(LL up){
    LL cnt=0;
    for(int i=1;i<=n;i++){
        LL now=get__(i,up);
        if(now<0)return 0;
        cnt+=now;
        if(cnt>k)return 0;
    }
    return (cnt<=k);
}
int main(){
    T=read();
    while(T--){
        n=read(),k=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),b[i]=read(),c[i]=read();
        l=-INF,r=INF,Ans=-INF;
        while(l<=r){
            LL mid=(l+r)>>1;
            if(check(mid))Ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<Ans<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！