题目传送门
题目大意
求一个满足$d\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d} \right \rceil - \sum_{i = 1}^{n} a_{i} \leqslant K$的最大正整数$d$。
整理一下可以得到条件是$d\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d} \right \rceil \leqslant K + \sum_{i = 1}^{n} a_{i}$
有注意到$\left \lceil \frac{a_i}{d} \right \rceil$的取值个数不会超过$2\left \lceil \sqrt{a_i} \right \rceil$。
证明考虑对于$1 \leqslant d \leqslant \left \lceil \sqrt{a_i} \right \rceil$，至多根号种取值，当$d >\left \lceil \sqrt{a_i} \right \rceil$的时候，取值至多为$1, 2, \cdots, \left \lceil \sqrt{a_i} \right \rceil$，所以总共不会超过$2\left \lceil \sqrt{a_i} \right \rceil$个取值。
所以我们把所有$\left \lceil \frac{a_i}{d} \right \rceil$的取值当成一个点，安插在数轴上，排个序，就愉快地找到了所有分段了。因为每一段内的$d$都是等价的，所以只需要用每一段的左端点计算和，然后判断$\left \lfloor \frac{K + \sum_{i = 1}^{n} a_{i}}{\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d} \right \rceil} \right \rfloor$是否在区间内，如果是就用它去更新答案。
Code
/**
* Codeforces
* Problem#831F
* Accepted
* Time:997ms
* Memory:100400k
*/
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <stack>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
const signed int inf = (signed)((1u << ) - );
const signed long long llf = (signed long long)((1ull << ) - );
const double eps = 1e-;
const int binary_limit = ;
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
template<typename T>
inline boolean readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) {
ungetc(x, stdin);
return false;
}
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
return true;
} #define LL long long int n;
LL C;
int* a;
vector<LL> seg; template<typename T>
T ceil(T a, T b) {
return (a + b - ) / b;
} inline void init() {
readInteger(n);
readInteger(C);
seg.push_back();
a = new int[(n + )];
for(int i = , x; i <= n; i++) {
readInteger(a[i]);
for(int j = ; j * j <= a[i]; j++)
seg.push_back(j), seg.push_back(ceil(a[i], j));
C += a[i];
}
seg.push_back(llf);
} LL res = ;
inline void solve() {
sort(seg.begin(), seg.end());
int m = unique(seg.begin(), seg.end()) - seg.begin() - ;
for(int i = ; i < m; i++) {
LL l = seg[i], r = seg[i + ], temp = ;
for(int i = ; i <= n; i++)
temp += ceil((LL)a[i], l);
LL d = C / temp;
if(d >= l && d < r && d > res)
res = d;
}
printf(Auto"\n", res);
} int main() {
init();
solve();
return ;
}
Brute force
然后我们来讲点神仙做法。 orz orz orz.....
不妨设$C = K + \sum_{i = 1}^{n} a_{i}$
因为所有$\left \lceil \frac{a_i}{d} \right \rceil \geqslant 1$，所以$d\leqslant \left \lfloor \frac{C}{n} \right \rfloor$
设$d_0 = \left \lfloor \frac{C}{n} \right \rfloor$。
假装已经顺利地求出了$d_0, d_1, d_2, \cdots, d_k$，我们找到最大的$d_{k + 1}$满足：
$d_{k + 1}\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d_k} \right \rceil \leqslant C$
当$d_{k + 1} = d_k$的时候我们就找到最优解了。
感觉很玄学？那我来证明一下。
定理1 $d_{k + 1} \leqslant d_{k}$
证明
- 当$k = 0$的时候，因为$\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d_0} \right \rceil \geqslant n$，所以$d_{1} = \left \lfloor \frac{C}{\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d_0} \right \rceil} \right \rfloor \leqslant \left \lfloor\frac{C}{n}\right \rfloor = d_0$。
- 当$k > 0$的时候，假设当$k = m - 1, (m \geqslant 0)$时成立，考虑当$k = m$的时候，由$d_{k} \leqslant d_{k - 1}$可得$\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d_{k - 1}} \right \rceil \leqslant \sum_{i = 1}^{n} \left \lceil \frac{a_i}{d_{k}} \right \rceil $，然后可得$d_{k + 1} \leqslant d_k$。
定理2 当$d_{k + 1} = d_{k}$，$d_k$是最优解
证明 假设存在$d > d_k$满足条件
- 显然$d \leqslant d_0$。（不然直接不合法）
- 显然$d \neq d_j\ \ (0 \leqslant j < k)$。
- 假设$d_{j} < d < d_{j - 1}\ \ (0 < j \leqslant k)$，那么$C \geqslant d\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d} \right \rceil \geqslant d\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d_{j}} \right \rceil $
由迭代做法可知$d\leqslant d_{j + 1}\leqslant d_j$，矛盾。
显然$d = d_k$时是合法的，所以$d_k$是最优解。
时间复杂度感觉很低，但是我只会证它不超过$O(n\sqrt{\frac{C}{n}})$
Code
/**
* Codeforces
* Problem#831F
* Accepted
* Time: 31ms
* Memory: 0k
*/
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long const int N = ; int n;
ll C;
int ar[N]; inline void init() {
scanf("%d"Auto, &n, &C);
for (int i = ; i < n; i++)
scanf("%d", ar + i), C += ar[i];
} ll ceil(ll a, ll b) {
return (a + b - ) / b;
} inline void solve() {
ll dcur = C / n, dans;
do {
swap(dcur, dans), dcur = ;
for (int i = ; i < n; i++)
dcur += ceil(ar[i], dans);
dcur = C / dcur;
} while (dcur != dans);
printf(Auto"\n", dans);
} int main() {
init();
solve();
return ;
}
更新日志
- 2018-1-28 补上jmr的做法
- 2018-10-22 给出证明