首页 > 代码库 > Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力
Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力
Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are n bamboos in a row, and the i-th from the left is ai meters high.
Vladimir has just planted n bamboos in a row, each of which has height 0 meters right now, but they grow 1 meter each day. In order to make the partition nice Vladimir can cut each bamboo once at any height (no greater that the height of the bamboo), and then the bamboo will stop growing.
Vladimir wants to check the bamboos each d days (i.e. d days after he planted, then after 2d days and so on), and cut the bamboos that reached the required height. Vladimir wants the total length of bamboo parts he will cut off to be no greater than k meters.
What is the maximum value d he can choose so that he can achieve what he wants without cutting off more than k meters of bamboo?
The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1011) — the number of bamboos and the maximum total length of cut parts, in meters.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the required heights of bamboos, in meters.
Print a single integer — the maximum value of d such that Vladimir can reach his goal.
3 4
1 3 5
3
3 40
10 30 50
32
In the first example Vladimir can check bamboos each 3 days. Then he will cut the first and the second bamboos after 3 days, and the third bamboo after 6 days. The total length of cut parts is 2 + 0 + 1 = 3 meters.
题目大意 求这样一个最大的d使得
整理一下可以得到条件是
有注意到的取值个数为。
还是说明一下,设。
1)当时,显然至多个取值。
2)当时,显然有,这个的取值个数也是的。
因此可以发现当d等于一个值的时候可能和另一个d值的时候是等价的。
所以我们把所有的取值当成一个点,安插在数轴上,然后一段一段地进行枚举。因为每一段内的d都是等价的,所以只需要用每一段的左端点计算和,然后判断是否在区间内,如果是就用它去更新答案。
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"\n", res); 97 } 98 99 int main() {100 init();101 solve();102 return 0;103 }
Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力