codeforces792E Colored Ball(贪心加枚举)

There are n boxes with colored balls on the table. Colors are numbered from 1 to n. i-th box contains ai balls, all of which have color i. You have to write a program that will divide all balls into sets such that: each ball belongs to exactly one of the sets, there are no empty sets, there is no set containing two (or more) balls of different colors (each set contains only balls of one color), there are no two sets such that the difference between their sizes is greater than 1. Print the minimum possible number of sets. Input The first line contains one integer number n (1 ≤ n ≤ 500). The second line contains n integer numbers a1, a2, ... , an (1 ≤ ai ≤ 109). Output

Print one integer number — the minimum possible number of sets.

题目意思：

把每种颜色的球分成划分成相差不到1 的集合，问最少能分多少组

思路：

这题需要枚举一个集合的容量x，显然x<=最少的颜色球的数量MIN+1，所以枚举范围为（1，MIN+1），所以每i次枚举的数x为MIN/i和MIN/i+1（x和x-1包含在这个情况中）,

然后判断是否都能分成，k=a[i]/x;    b=a[i]%x;两种情况可以表示能分成

1：b=0，刚好整除，分成k种

2：b+k>=x-1,已经分好k组，每组拿1个给剩余的b，若这都能大于等于x-1，那么肯定能分成有x的也有x-1的组合，这种分成k+1种

以下为代码：

#include <cstdio> #include <cmath> #include <iostream> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <map> #include <numeric> #include <set> #include <string> #include <cctype> #include <sstream> #define INF 0x3f3f3f3f typedef long long LL; using namespace std; const int maxn=500+5; int n,a[maxn]; LL ans; bool ok(int x)//x为一个set的容量 { ans=0; int k,b; for (int i=0;i<n;i++){ k=a[i]/x; b=a[i]%x; if (!b) { ans+=k; } else if (k+b>=x-1){ ans+=(k+1); } else return 0; } return 1; } int main () { int MIN=INF; scanf ("%d",&n); for (int i=0;i<n;i++){ scanf ("%d",&a[i]); if (a[i]<MIN) MIN=a[i]; } for (int i=1;i<=MIN;i++){ if (ok(MIN/i+1)||ok(MIN/i)){ printf ("%lld\n",ans); break; } } return 0; }