2018江苏冬令营2 ：UPC 石子游戏 (贪心)

本文主要是介绍2018江苏冬令营2 ：UPC 石子游戏 (贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

石子游戏

时间限制: 1 Sec 内存限制: 128 MB
提交: 118 解决: 32
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

在Bob学会怎样玩Nim Game之后，他打算尝试另一款看起来更为简单的石子游戏
这个游戏是这样子玩的：一共有一个玩家，且一开始有N堆石头，第i堆石头有ai个石子。玩家每次只能移动一个石子从一堆到另一堆。在每次移动结束后，如果存在一个整数x(x>1)满足任意一堆的当前石子数bi都是x的倍数，那么游戏结束。现在你需要帮助Bob计算出为了结束这个无聊的游戏，他最少需要移动的次数。特别的， 0是任何正整数的倍数。

输入

第一行一个整数N，表示石子的堆数
第二行N个整数，表示每堆石子的数量

输出

一行一个整数，即最少的移动次数。如果一开始就满足游戏结束的条件，请输出0

样例输入


1 2 3 4 5

样例输出

提示

从第1堆移动一个到第5堆，从第4堆移动一个到第2堆
得到：0 3 3 3 6
满足都是3的倍数
数据规模
对于30%的数据，1<=N<=100
对于60%的数据，1<=N<=5000
对于100%的数据，1<=N<=100,000，1<=ai<=100,000

来源

2018江苏冬令营2

【思路】

起初以为是个博弈，分析了后，题目要求是 n个数是某个x的倍数，也就是说他们的GCD >1

所以可以枚举素数，然后对可以满足的情况进行分析，把% 后的从小的往大的上放

【code】

#include <iostream>
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const ll INF=(1ll<<63-1);
const int MAXN=5e5+5;using namespace std;
int vis[MAXN];
ll a[MAXN];
ll b[MAXN];
ll prime[MAXN];
int cont;
void init()
{mem(vis,0);cont=0;for(int i=2;i<=1e6+10;i++){if(!vis[i]){prime[++cont]=i;}for(int j=1;j<=cont&&i*prime[j]<=1e6+10;j++){vis[ i*prime[j]] =1;if((i%prime[j])==0)break;}}
}int main()
{init();int n;cin>>n;ll sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}int c=0;ll av=sum/n;for(int i=1;i<=n;i++){if(a[i]%av==0)c++;}if(c==n){cout<<0<<endl;return 0;}ll ans=INF;for(int i=1;i<=cont;i++){if(sum%prime[i]==0){ll s=0;mem(b,0);for(int j=1;j<=n;j++){b[j]=a[j]%prime[i];s+=b[j];}s=s/prime[i];sort(b+1,b+n+1);ll res=0,s2=0,s3=0;for(int j=n;j>=1;j--){s3+= (b[j]+prime[i]-b[j]%prime[i]);s2= s3/prime[i];res+= (prime[i]-b[j]%prime[i]);if(s2==s){ans=min(ans,res);break;}}}}cout<<ans<<endl;return 0;
}

1223

这篇关于2018江苏冬令营2 ：UPC 石子游戏 (贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！