题解：CF2279C Anti-Productive

The_jester_from_Lst · 2026-11-10 15:47:49 · 题解

题目要求任意两个数的乘积小于 l，也就是要求最大值和次大值相乘小于 l。发现合法的次大值一定不超过 \sqrt l。否则次大最大都超过 \sqrt l 乘积一定大于 l。则我们可以枚举次大值 x。对于一个次大值，要使整个序列 a 合法即要使所有大于 x 的数中最大值减小至 \lfloor\frac{l}{x} \rfloor，其余都要减小至 x。双指针维护这些数的和即可。注意特判最大值小于 \lfloor\frac{l}{x} \rfloor 的情况，此时最大值不用变。

附上代码。

#pragma GCC optimize("Ofast", "fast-math", "unroll-loops", "no-stack-protector", "inline")
#include<bits/stdc++.h>
#include<ext/rope>
#define int long long
#define ull unsigned long long
#define uint unsigned int
#define il inline
#define mk make_pair
#define fir first
#define sec second
#define pb emplace_back
#define put putchar
#define sz(x) (int)(x.size())
using namespace std;
using namespace __gnu_cxx;
typedef pair<int,int> pii;
il int rd(){
    int jya=0,tl=1;char jyt=getchar();
    while(!isdigit(jyt)){if(jyt=='-')tl=-1;jyt=getchar();}
    while(isdigit(jyt)){jya=(jya<<1)+(jya<<3)+(jyt-'0');jyt=getchar();}
    return jya*tl;
}
il void wr(int jjy){
    if(jjy<0)put('-'),jjy=-jjy;
    if(jjy>9)wr(jjy/10);
    putchar(jjy%10+48);
}
const int JYAAKIOI=1e18,N=5e5+5,B=320,mod=998244353;
int n,l,a[N];
il void jyacanfly(int testid){
    n=rd();l=rd();
    for(int i=1;i<=n;++i)a[i]=rd();
    sort(a+1,a+n+1);
    int sql=0;
    if(l>1){
        sql=sqrt(l-1);
        while((sql+1)*(sql+1)<=l-1)++sql;
        while(sql*sql>l-1)--sql;
    }
    int mx=min(a[n],sql),ans=JYAAKIOI,p=1,sum=0;
    for(int i=1;i<n;++i)sum+=a[i];
    for(int x=0;x<=mx;++x){
        while(p<n&&a[p]<=x){
            sum-=a[p];
            ++p;
        }
        if(x==0){
            int cst=sum;
            ans=min(ans,cst);
        }
        else{
            int y=(l-1)/x;
            y=min(y,a[n]);
            if(y<=x){
                int cst=sum-(n-p)*x;
                if(a[n]>x)cst+=a[n]-x;
                ans=min(ans,cst);
            }
            else{
                int cst=(a[n]-y)+sum-(n-p)*x;
                ans=min(ans,cst);
            }
        }
    }
    wr(ans),put('\n');
}
signed main(){
//    freopen("rotate.in","r",stdin);
//    freopen("rotate.out","w",stdout);
    int c=0,T=rd();
    for(int _=1;_<=T;++_)jyacanfly(_);
    return 0;
}