1706D1 - Chopping Carrots (Easy Version)

原题链接：

Problem - 1706D1 - Codeforces

题目描述：

This is the easy version of the problem. The only difference between the versions is the constraints on nn, kk, aiai, and the sum of nn over all test cases. You can make hacks only if both versions of the problem are solved.

Note the unusual memory limit.

You are given an array of integers a1,a2,…,ana1,a2,…,an of length nn, and an integer kk.

The cost of an array of integers p1,p2,…,pnp1,p2,…,pn of length nn is

max1≤i≤n(⌊aipi⌋)−min1≤i≤n(⌊aipi⌋).max1≤i≤n(⌊aipi⌋)−min1≤i≤n(⌊aipi⌋).

Here, ⌊xy⌋⌊xy⌋ denotes the integer part of the division of xx by yy. Find the minimum cost of an array pp such that 1≤pi≤k1≤pi≤k for all 1≤i≤n1≤i≤n.

Input

The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases.

The first line of each test case contains two integers nn and kk (1≤n,k≤30001≤n,k≤3000).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤a1≤a2≤…≤an≤30001≤a1≤a2≤…≤an≤3000).

It is guaranteed that the sum of nn over all test cases does not exceed 30003000.

Output

For each test case, print a single integer — the minimum possible cost of an array pp satisfying the condition above.

题目大意：

给定一个数组a，给定一个k，请你构造一个数组p，使得最大的a[i]/p[i]和最小的a[i]/p[i]之间的差值尽量小，注意p[i]不得大于k。

解题思路：

枚举最小值minV，然后我们需要取尽可能大的p[i]，使得每个a[i]/p[i]大于等于minV。然后维护答案即可。

 特例：如果给出的k大于数组a的最大值的话，我们可以把整个数组p都取k，那么所有的a[i]/p[i]都为0，所以答案直接输出0即可

代码（CPP）：

#include 
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 3e3 + 10;
const int INF = 0x3fffffff;
int n, a[maxn], p[maxn], k;
 
/*
    枚举最小值minV，然后我们需要取尽可能大的p[i]，使得每个a[i]/p[i]大于等于minV。然后维护答案即可。
    特例：如果给出的k大于数组a的最大值的话，我们可以把整个数组p都取k，那么所有的a[i]/p[i]都为0，所以答案直接输出0即可。
*/
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);
 
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n);
        if(k > a[n])
            cout << 0 << endl;
        else
        {
            int ans = INF;
            for (int minV = 1; minV <= a[1]; minV++)
            {
                int Max = -1, Min = INF;
                for (int i = 1; i <= n; i++)
                {
                    p[i] = a[i] / minV;
                    if (p[i] > k)
                        p[i] = k;
                    Max = max(Max, a[i] / p[i]);
                    Min = min(Min, a[i] / p[i]);
                }
                ans = min(Max - Min, ans);
            }
            cout << ans << endl;
        }
    }
    return 0;
}