codeforces#1305F. Kuroni and the Punishment(随机算法)
题目链接:
https://codeforces.com/contest/1305/problem/F
题意:
给出$n$个数,最少执行多少次操作可以使得$n$个数最大公约数不为1
每次操作可以给某个数加一或者减一
分析:
由于因子为$2$时,最多需要执行$n$次操作
所以在寻找到最优因子的情况下,执行两次操作的数的数量不可能多于$\frac{1}{2}$
那么任意选择数组中的一个数$a[i]$,最优因子是$a[i],a[i]+1,a[i]-1$的因子的概率是$\frac{1}{2}$
那么在数组随机选出$100$个数,最优因子不是他们因子的概率是$\left (\frac{1}{2} \right )^{100}$
注意:rand()返回的是1到32767的随机数,想要产生1到2e5的随机数需要两个rand相乘
AC代码:
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=b;i>=a;i--) #define pb push_back #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef long long ll; typedef vector<int> VI; typedef pair<int,int> PII; const int maxn=2e5+7; const int INF=1e9+10; set<ll>se; int n; ll a[maxn]; void add(ll x){ for(ll i=2;i*i<=x;i++){ if(x%i==0){ se.insert(i); while(x%i==0)x/=i; } } if(x!=1)se.insert(x); } ll cal(ll x){ ll res=0; rep(i,1,n){ if(a[i]>=x)res+=min(a[i]%x,x-a[i]%x); else res+=x-a[i]%x; if(res>=n)return n; } // cout<<x<<" "<<res<<endl; return res; } int main() { srand((unsigned)time(NULL)); scanf("%d",&n); rep(i,1,n)scanf("%lld",&a[i]); rep(i,1,10*n){//随机打乱数组的顺序 int x=(ll)rand()*rand()%n+1; int y=(ll)rand()*rand()%n+1; swap(a[x],a[y]); } rep(i,1,min(100,n)){ add(a[i]); add(a[i]+1); if(a[i]-1>=2)add(a[i]-1); } ll ans=n; se.insert(2); for(auto i:se){ // cout<<i<<endl; ans=min(ans,cal(i)); } printf("%lld\n",ans); return 0; }
相关推荐
Happyunlimited 2020-04-30
风吹夏天 2020-01-24
yedaoxiaodi 2020-01-06
魏莉的微 2019-12-19
baike 2019-12-19
shawsun 2019-12-15
baike 2019-12-08
微分 2018-03-02
Qunicy 2019-07-09
郭岚 2019-06-28
YUAN 2019-06-28
ZhuZhuWonder 2019-06-17
MachineIntellect 2015-07-10
蜗牛慢爬的李成广 2019-05-12
StrongHYQ 2018-07-01