Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F)

题目传送门

　　传送门I

　　传送门II

　　传送门III

题目大意

　　求一个满足$dsum_{i = 1}^{n} left lceil frac{a_i}{d} ight ceil - sum_{i = 1}^{n} a_{i} leqslant K$的最大正整数$d$。

　　整理一下可以得到条件是$dsum_{i = 1}^{n} left lceil frac{a_i}{d} ight ceil leqslant K + sum_{i = 1}^{n} a_{i}$

　　有注意到$left lceil frac{a_i}{d} ight ceil$的取值个数不会超过$2left lceil sqrt{a_i} ight ceil$。

　　证明考虑对于$1 leqslant d leqslant left lceil sqrt{a_i} ight ceil$，至多根号种取值，当$d >left lceil sqrt{a_i} ight ceil$的时候，取值至多为$1, 2, cdots, left lceil sqrt{a_i} ight ceil$，所以总共不会超过$2left lceil sqrt{a_i} ight ceil$个取值。

　　所以我们把所有$left lceil frac{a_i}{d} ight ceil$的取值当成一个点，安插在数轴上，排个序，就愉快地找到了所有分段了。因为每一段内的$d$都是等价的，所以只需要用每一段的左端点计算和，然后判断$left lfloor frac{K + sum_{i = 1}^{n} a_{i}}{sum_{i = 1}^{n} left lceil frac{a_i}{d} ight ceil} ight floor$是否在区间内，如果是就用它去更新答案。

Code

  1 /**
  2  * Codeforces
  3  * Problem#831F
  4  * Accepted
  5  * Time:997ms
  6  * Memory:100400k
  7  */
  8 #include <iostream>
  9 #include <cstdio>
 10 #include <ctime>
 11 #include <cmath>
 12 #include <cctype>
 13 #include <cstring>
 14 #include <cstdlib>
 15 #include <fstream>
 16 #include <sstream>
 17 #include <algorithm>
 18 #include <map>
 19 #include <set>
 20 #include <stack>
 21 #include <queue>
 22 #include <vector>
 23 #include <stack>
 24 #ifndef WIN32
 25 #define Auto "%lld"
 26 #else
 27 #define Auto "%I64d"
 28 #endif
 29 using namespace std;
 30 typedef bool boolean;
 31 const signed int inf = (signed)((1u << 31) - 1);
 32 const signed long long llf = (signed long long)((1ull << 63) - 1);
 33 const double eps = 1e-6;
 34 const int binary_limit = 128;
 35 #define smin(a, b) a = min(a, b)
 36 #define smax(a, b) a = max(a, b)
 37 #define max3(a, b, c) max(a, max(b, c))
 38 #define min3(a, b, c) min(a, min(b, c))
 39 template<typename T>
 40 inline boolean readInteger(T& u){
 41     char x;
 42     int aFlag = 1;
 43     while(!isdigit((x = getchar())) && x != '-' && x != -1);
 44     if(x == -1) {
 45         ungetc(x, stdin);    
 46         return false;
 47     }
 48     if(x == '-'){
 49         x = getchar();
 50         aFlag = -1;
 51     }
 52     for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0');
 53     ungetc(x, stdin);
 54     u *= aFlag;
 55     return true;
 56 }
 57 
 58 #define LL long long
 59 
 60 int n;
 61 LL C;
 62 int* a;
 63 vector<LL> seg;
 64 
 65 template<typename T>
 66 T ceil(T a, T b) {
 67     return (a + b - 1) / b;
 68 }
 69 
 70 inline void init() {
 71     readInteger(n);
 72     readInteger(C);
 73     seg.push_back(1);
 74     a = new int[(n + 1)];
 75     for(int i = 1, x; i <= n; i++) {
 76         readInteger(a[i]);
 77         for(int j = 1; j * j <= a[i]; j++)
 78             seg.push_back(j), seg.push_back(ceil(a[i], j));
 79         C += a[i];
 80     }
 81     seg.push_back(llf);
 82 }
 83 
 84 LL res = 1;
 85 inline void solve() {
 86     sort(seg.begin(), seg.end());
 87     int m = unique(seg.begin(), seg.end()) - seg.begin() - 1;
 88     for(int i = 0; i < m; i++) {
 89         LL l = seg[i], r = seg[i + 1], temp = 0;
 90         for(int i = 1; i <= n; i++)
 91             temp += ceil((LL)a[i], l);
 92         LL d = C / temp;
 93         if(d >= l && d < r && d > res)
 94             res = d;
 95     }
 96     printf(Auto"
", res);
 97 }
 98 
 99 int main() {
100     init();
101     solve();
102     return 0;
103 }

Brute force

　　然后我们来讲点神仙做法。142857 orz orz orz.....

　　不妨设$C = K + sum_{i = 1}^{n} a_{i}$

　　因为所有$left lceil frac{a_i}{d} ight ceil geqslant 1$，所以$dleqslant left lfloor frac{C}{n} ight floor$

　　设$d_0 = left lfloor frac{C}{n} ight floor$。

　　假装已经顺利地求出了$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} ight ceil 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} ight ceil geqslant n$，所以$d_{1} = left lfloor frac{C}{sum_{i = 1}^{n} left lceil frac{a_i}{d_0} ight ceil} ight floor leqslant left lfloorfrac{C}{n} ight floor = 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}} ight ceil leqslant sum_{i = 1}^{n} left lceil frac{a_i}{d_{k}} ight ceil $，然后可得$d_{k + 1} leqslant d_k$。

定理2 当$d_{k + 1} = d_{k}$，$d_k$是最优解

　　证明假设存在$d > d_k$满足条件

显然$d leqslant d_0$。（不然直接不合法）
显然$d eq d_j (0 leqslant j < k)$。
假设$d_{j} < d < d_{j - 1} (0 < j leqslant k)$，那么$C geqslant dsum_{i = 1}^{n} left lceil frac{a_i}{d} ight ceil geqslant dsum_{i = 1}^{n} left lceil frac{a_i}{d_{j}} ight ceil $
由迭代做法可知$dleqslant d_{j + 1}leqslant d_j$，矛盾。

　　显然$d = d_k$时是合法的，所以$d_k$是最优解。

　　时间复杂度感觉很低，但是我只会证它不超过$O(nsqrt{frac{C}{n}})$

Code

 1 /**
 2  * Codeforces
 3  * Problem#831F
 4  * Accepted
 5  * Time: 31ms
 6  * Memory: 0k
 7  */
 8 #include <iostream>
 9 #include <cassert>
10 #include <cstdlib>
11 #include <cstdio>
12 #include <vector>
13 #include <queue>
14 #ifndef WIN32
15 #define Auto "%lld"
16 #else
17 #define Auto "%I64d"
18 #endif
19 using namespace std;
20 typedef bool boolean;
21 
22 #define ll long long
23 
24 const int N = 105;
25 
26 int n;
27 ll C;
28 int ar[N];
29 
30 inline void init() {
31     scanf("%d"Auto, &n, &C);
32     for (int i = 0; i < n; i++)
33         scanf("%d", ar + i), C += ar[i];
34 }
35 
36 ll ceil(ll a, ll b) {
37     return (a + b - 1) / b;
38 }
39 
40 inline void solve() {
41     ll dcur = C / n, dans;
42     do {
43         swap(dcur, dans), dcur = 0;
44         for (int i = 0; i < n; i++)
45             dcur += ceil(ar[i], dans);
46         dcur = C / dcur;
47     } while (dcur != dans);
48     printf(Auto"
", dans);
49 }
50 
51 int main() {
52     init();
53     solve();
54     return 0;
55 }

更新日志

2018-1-28 补上jmr的做法
2018-10-22 给出证明