[CF2144D] Price Tags 题解

aeiouaoeiu · 2025-11-19 10:52:32 · 题解

若 c_i 的标签能被现有标签替换，则需要满足 \displaystyle\lceil\frac {c_i}x\rceil=c_j，进一步可得 c_i\in[x(c_j-1)+1,xc_j]。于是枚举 x，然后枚举 x 的倍数 k，设 b_i 表示满足 c_j=i 的 j 的个数，则能被节省的标签数量为 \displaystyle\sum_k \min(b_k,\sum_{i=x(k-1)+1}^{xk}b_i)，可以前缀和求出。

现在知道了除数取 x 时能节省多少标签，还需要知道此时的净收益。仿照前文，\displaystyle\lceil\frac {c_i}x\rceil=k\iff c_i\in[x(k-1)+1,xk]，同理枚举 x,k 用前缀和求出即可。

时间复杂度调和级数级。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=1000007,V=500000,ee=1e18;
ll n,y,c[maxn],buc[maxn],su[maxn],b1[maxn],b2[maxn],ans;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        for(ll i=1;i<maxn;i++) su[i]=buc[i]=b1[i]=b2[i]=0;
        cin>>n>>y,ans=-ee;
        for(ll i=1;i<=n;i++) cin>>c[i],buc[c[i]]++;
        for(ll i=1;i<maxn;i++) su[i]=buc[i]+su[i-1];
        for(ll x=2;x<=V;x++){
            for(ll k=1;k*x<=V;k++){
                b1[x]+=k*(su[min(V,k*x)]-su[(k-1)*x]);
                b2[x]+=min(su[min(V,k*x)]-su[(k-1)*x],buc[k]);
            }
        }
        //cout<<buc[1]<<"\n";
        for(ll i=2;i<=V;i++) ans=max(ans,b1[i]-(n-b2[i])*y);
        cout<<ans<<"\n";
    }
    return 0;
}

::::