专栏文章

[CF2144D] Price Tags 题解

aaeiouaoeiu
CF2144D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5768y
此快照首次捕获于
2025/12/01 20:45
3 个月前
此快照最后确认于
2025/12/01 20:45
3 个月前
查看原文
若 cic_i 的标签能被现有标签替换，则需要满足 ⌈cix⌉=cj\displaystyle\lceil\frac {c_i}x\rceil=c_j，进一步可得 ci∈[x(cj−1)+1,xcj]c_i\in[x(c_j-1)+1,xc_j]。于是枚举 xx，然后枚举 xx 的倍数 kk，设 bib_i 表示满足 cj=ic_j=i 的 jj 的个数，则能被节省的标签数量为 ∑kmin⁡(bk,∑i=x(k−1)+1xkbi)\displaystyle\sum_k \min(b_k,\sum_{i=x(k-1)+1}^{xk}b_i)，可以前缀和求出。
现在知道了除数取 xx 时能节省多少标签，还需要知道此时的净收益。仿照前文，⌈cix⌉=k  ⟺  ci∈[x(k−1)+1,xk]\displaystyle\lceil\frac {c_i}x\rceil=k\iff c_i\in[x(k-1)+1,xk]，同理枚举 x,kx,k 用前缀和求出即可。
时间复杂度调和级数级。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...