【CodeForces】【数学】【贪心】792E Colored Balls

CodeForces 792E Colored Balls

题目大意

将$N$个数中，每个数分成若干个数的和，要求必须由$x,x?1$构成。求出最少分出的集合个数。

分析

设我们最终从$A_i$分出的数的数量为$k$，分出的数为$x,x?1$。则我们可以 通过打表 得到：$k\le \sqrt{A_i}$且有$x\le \sqrt{A_i}$，且$x$越大越好。

这告诉我们可以暴力枚举每块的大小。

我们将$A$排序后来搞（因为$x$最大不能够超过$A_1$）。

然后我们暴力枚举$k$（即第一个数分开的个数，不超过$\sqrt{A_1}$），然后检验对于每个数是否成立，这时$x$可以等于$?\frac{A_1}{k}?+1$或者$?\frac{A_1}{k}?$。

当一个数$A_i$能被$x,x?1$分开时，令$a=?\frac{A_i}{x}?,b=A_i\mathrm{m}\mathrm{o}\mathrm{d}x$，那么我们可以得到，当$b=0$或者$a+b\ge x?1$时$A_i$可以被$x,x?1$分开。

就这样检验就可以了。

打表大法好啊！！！

参考代码

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 500;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;int N;
int A[Maxn + 5];void check(int siz) {
    ll sum = 0;for(int i = 1; i <= N; i++) {
    int p = A[i] / siz, q = A[i] % siz;if(q == 0 || p + q >= siz - 1)sum += p + (q != 0);else return;}printf("%lld\n", sum);exit(0);
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &N);for(int i = 1; i <= N; i++)scanf("%d", &A[i]);sort(A + 1, A + N + 1);int ans = INF;for(int i = 1; i * i <= A[1]; i++) {
    check(A[1] / i + 1);check(A[1] / i);}printf("%d\n", ans);return 0;
}