[CF792E] Colored Balls

18.10.02模拟赛T3。

lxd找的这道题还是挺有意思的。

一个类似贪心的算法，枚举min的因数进行check。

check的时候枚举所有颜色即可。

貌似很简单的样子，然而我只用exgcd写了40分......

上代码。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define ll long long
 5 using namespace std;
 6 
 7 int n;
 8 ll a[505];
 9 ll mn=0x3f3f3f3f;
10 ll ans;
11 
12 int check(int k)
13 {
14     ll ret=0;
15     for(int i=1;i<=n;i++)
16     {
17         int c=a[i]%k;
18         int d=a[i]/k;
19         if(c!=0&&(c+d)<(k-1))
20         {
21             return 0;
22         }
23         ret+=d+(c!=0);
24     }
25     ans=ret;
26     return 1;
27 }
28 
29 int main()
30 {
31     scanf("%d",&n);
32     for(int i=1;i<=n;i++)scanf("%I64d",&a[i]),mn=min(mn,a[i]);
33     for(int i=1;i<=mn;i++)
34     {
35         int fl=check(mn/i+1)||check(mn/i)||check(mn/i-1);
36         if(fl)break;
37     }
38     printf("%I64d",ans);
39     return 0;
40 }