Codeforces 1706D1. Codeforces Round #809 (Div. 2) D1(二分)
原题链接
中等
作者:
小小_88
,
2023-01-25 22:12:43
,
所有人可见
,
阅读 168
Chopping Carrots (Easy Version)
C++ 代码
/*
本题的数据较小,支持 n^2 以上的算法,因此考虑枚举所有最小值。
对于每个最小值去求一下尽可能小的最大值,然后更新答案取一个差值最小的。
可以发现根据 p 的变化,a[i] / p 的变化是单调的,因此可以用二分,对于每个最小值 mn,
每一位都二分出 > mn 的最小的 a[i] / p,所有的 a[i] / p 的最大值就是当前能取得最小的
最大值,用差值更新答案
至于如何枚举最小值,由于 a[0] 是最小的,因此 a[0] / (1 ~ k) 就是所有能取到的最小值。
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
void work()
{
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
if(n == 1 || a[n - 1] < k)
{
puts("0");
return;
}
int res = 1e9;
for(int i = a[0] / k; i <= a[0]; i++)
{
int mx = 0;
bool st = true;
for(int j = 0; j < n; j++)
{
int l = 1, r = k;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[j] / mid >= i) l = mid;
else r = mid - 1;
}
mx = max(mx, a[j] / r);
}
if(st) res = min(res, mx - i);
}
printf("%d\n", res);
}
int main()
{
int T;
scanf("%d", &T);
while(T--) work();
return 0;
}