题意简述:
给定长度为 n 的数组 a_i。每次你可以花费 1 的代价使 a_i 加上或者减去 1。要求最小化代价使得所有 a_i 都是质数 k 的倍数。n \leq 10^5,\ a_i \leq 10^{12}。
思路分析:
首先我们令 k = 2,得到 ans \leq n。也就是说,对于最优解的画面,至多有 \lfloor \frac n 2 \rfloor 个整数的变化幅度超过 1。
设定阀值 \omega,我们随机从 a_{1 \dots n} 中选择 k 个数 x_{1 \dots k},每次检查 x-1,x,x+1 的每个质因子是否为答案。复杂度为 O(n \sigma (a) \times \omega),正确率为 1 – (\frac 1 2)^{\omega}。
细节分析:
- 可以用通过
clock()
函数控制循环次数。本题时限2.50s,实测time_limit
设为 0.10s 可通过本题。 -
由于洛谷对于CF题目采用RemoteJudge方式评测,即将代码发回CF测评,考虑到CF采用windows环境评测,
rand()
函数的取值范围在 [0, 32767],考虑使用std::mt19937
替代。
模板代码:
std::mt19937 rng(20040725^std::chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
完整代码:
#include<bits/stdc++.h>
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
std::mt19937 rng(20040725^std::chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
const int N=2e5+10;
int n;
long long a[N];
std::set<long long> checked,calced;
long long check(long long x){
if(checked.count(x))return LLONG_MAX;
checked.insert(x);
long long ans=0;
for(int i=1;i<=n;i++)if(a[i]<=x){
ans+=x-a[i];
}else{
ans+=std::min(a[i]%x,x-a[i]%x);
}
return ans;
}
long long calc(long long x){
if(!x||calced.count(x))return LLONG_MAX;
calced.insert(x);
long long ans=LLONG_MAX;
// printf("check %lld => ",x);
for(long long i=2;i*i<=x;i++)if(x%i==0){
ans=std::min(ans,check(i));
while(x%i==0)x/=i;
}
if(x!=1)ans=std::min(ans,check(x));
// printf("œ%lld\n",ans);
return ans;
}
int main(){
#ifdef CF1305F
freopen("data.in","r",stdin);
#endif
read(n),srand(20040725);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=n;i>=1;i--)std::swap(a[i],a[rand(1,i)]);
long long ans=LLONG_MAX;
for(int k=1;k<=n&&clock()/(double)CLOCKS_PER_SEC<.1;k++){
ans=std::min(ans,calc(a[k]));
ans=std::min(ans,calc(a[k]+1));
ans=std::min(ans,calc(a[k]-1));
}
printf("%lld\n",ans);
}
0 Comments