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;
}