首页 > 其他 > 详细

2A - Stone

时间:2019-04-19 18:50:35      阅读:101      评论:0      收藏:0      [点我收藏+]

 

任意一堆移动过后的石子都是整数x的倍数,

那么石子总数显然也应该是x的倍数,

换句话说,x必为石子数总和的一个质因子.

题目要求移动次数尽量小,那么x也应该尽量小.

所以选择石子数总和的最小质因子.

对每堆石子数进行取模运算即可知道每堆石子需要移走或增加多少石子.

然后就可以开始模拟了.

把取模后的石子数进行从大到小的排序并求出取模后的石子总数,

然后求出可以组成x的个数.

用大石子堆到小石子堆去减这些x,在累加起来,即得到最少移动次数.

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 ll arr[100005];
 7 // 得到第一个质因子
 8 ll getFac(ll x)
 9 {
10     for (ll i = 2; i <= x; i++)
11         if (x % i == 0)
12             return i;
13     return -1;
14 }
15 
16 bool cmp(ll a, ll b)
17 {
18     return a >= b;
19 }
20 
21 int main()
22 {
23     ios::sync_with_stdio(false);
24     cin.tie(0);
25 
26     int n;
27     cin >> n;
28     ll sum = 0;
29     for (int i = 0; i < n; i++) {
30         cin >> arr[i];
31         sum += arr[i];
32     }
33 
34     // 最小质因子的余数系最小
35     ll num = getFac(sum);
36     sum = 0;
37     for (int i = 0; i < n; i++) {
38         arr[i] = arr[i] % num;
39         sum += arr[i];
40     }
41 
42     // 模拟
43     sort(arr, arr + n, cmp);
44     ll k = sum / num;
45     ll ans = 0;
46     for (int i = 0; i < k; i++) {
47         ans += num - arr[i];
48     }
49     cout << ans << endl;
50     return 0;
51 }

 

2A - Stone

原文:https://www.cnblogs.com/AntonLiu/p/10737686.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!