CF2104D 这个数组十分甚至九分滴漂亮

· · 题解

题意

有一个数组 a，你可以对其执行以下两种操作：

  1. 花费 1 个金币，使得任意一个 a_i \leftarrow a_i+1。
  2. 增加 1 个金币，使得任意一个 a_i\leftarrow a_i-1。

若一个数组非常滴理想，当且仅当其满足：

  1. 对于每一个 1\le i\le n，a_i\ge 2。
  2. 对于每一对 1\le i,j\le n，\gcd(a_i,a_j)=1。（若长度为 1 视为满足该条件）

当一个数组能够通过上述的两种操作变得理想，那它就漂亮滴很呐（赞赏）。

但是现在给你的这个长度为 n 的数组 a 可能不太漂亮（悲），但是没有关系，你可以删除其中的一些数字，让它重新变得漂亮。注意：不能先修改再删除。

求需要删除的数字的最小数量。

数据范围：1\le n\le 4\times 10^5,1\le a_i\le 10^9。

思路

非常容易就能看出，修改操作实际上就是在保持当前数组总和不大于原始总和的情况下随意改变数组元素。为什么是不大于？因为你可以把金币剩下来！然后我们小贪一波，要让这个数组互质且和最小，直接让它等于质数表前 n 项！这样子数组总和是最小的，我们剩的金币最多，操作空间就最大！而题目中给出的每一个元素至少为 2 的条件刚好也贴合最小的质数。

那么就很简单了，如果当前数组长度为 n，所有元素之和不小于质数表前 n 项之和，这个数组就是漂亮的。如果小于了，我们就应该考虑删除数字，很明显应该尽量删除小的数字，这样子我们数组总和的变化量就少，而因为长度缩短，要求贴合的质数表的长度也会缩短，而质数表是越来越大的，我们每次删除之后就更有机会超过质数表的前缀和，正确性是有的。

那么我们就先筛 4\times 10^5 个质数，然后做一下前缀和，然后在原数组上一直删就行了。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937 myrand(time(0));
inline ll read(){
    ll x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    static int sta[35];
    int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top)putchar(sta[--top]+'0');
}
ll n,a[400005],sum[400005];
vector<int>prime;
bitset<7000005>notprime;
void init(int mx){
    notprime[1]=1;
    for(int i=2;i<=mx;i++){
        if(!notprime[i])prime.push_back(i);
        for(auto val:prime){
            if(i*val>mx)break;
            notprime[i*val]=1;
            if(i%val==0)break;
        }
    }
}
inline void work(){
    n=read();
    ll val=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        val+=a[i];
    }
    if(n==1){puts("0");return;}
    sort(a+1,a+n+1);
    if(val>=sum[n]){puts("0");return;}
    for(int i=1;i<=n;i++){
        val-=a[i];
        if(val>=sum[n-i]){
            write(i);putchar('\n');return;
        }
    }
    write(n);putchar('\n');
}
int t;
int main(){
    t=read();
    init(7000000);
    for(int i=0;i<=400000;i++)sum[i+1]=sum[i]+prime[i];
    while(t--)work();
    return 0;
}

记录。