题目描述

塔姆博林准备了一个能让她变得更加健康的锻炼计划。

该计划被分为N个课程。

第i个课程的锻炼时长为$ M_i $分钟。

整个锻炼计划的每个课程的锻炼时长严格递增。

这个锻炼计划的难度等于任意两个连续的锻炼课程之间的锻炼时长（分钟数）之差的最大值。

为了降低锻炼难度，塔姆博林决定在她的锻炼计划中增加最多K个额外的锻炼课程。

她可以在健身计划中的任何位置安排这些额外课程。

所有课程的持续时长必须都是整数。

在添加了额外课程之后，整个锻炼计划的每个课程的锻炼时长必须仍然严格递增。

请计算锻炼计划的难度的最小可能值。

输入格式

第一行包含整数 T，表示共有T 组测试数据。

对于每组数据，第一行包含两个整数 N 和 K。

第二行包含N个整数，其中第i个表示 $ M_i $。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x为组别编号（从 1 开始），y为增加最多K 个额外课程后，锻炼计划的难度的最小可能值。

数据范围

$ 1≤T≤100 $,
$ 2≤N≤10^5 $,
$ 1≤Mi≤10^9 $,
$ M_i < M_i+1 $,
$ 1≤K≤10^5 $

样例

输入样例：

3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10

输出样例：

Case #1: 2
Case #2: 3
Case #3: 1

算法1

(二分) $O(nlogn)$

• 分为两步操作：

  • 先求解出最大的差值，即难度
  • 进行二分，check() 再当前难度下要添加的锻炼课程是否大于K

时间复杂度

二分嵌套循环， 时间复杂度即为 $O(nlogn)$

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

int n, k;
int a[N];

bool check(int mid)
{
    int cnt = 0;
    int last = a[0];
    int p = 1;

    while(p < n){
        if(a[p] - last > mid){
            cnt ++;
            last = last + mid;
        }else{
            last = a[p ++];
        }
    }
    return cnt <= k;
}

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T--){
        cin >> n >> k;
        for(int i = 0; i < n; i ++) cin >> a[i];

        int l = 0, r = 0;
        for(int i = 1; i < n; i ++) r = max(r, a[i] - a[i - 1]);
        while(l < r){
            int mid = l + r >> 1;
            //cout << mid << endl;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }

        printf("Case #%d: %d\n", cnt ++, r);
    }
    return 0;
}