题目描述

有N个数，可以往这N个数中间插K个数，使得相邻两数的绝对差最小，求最小绝对差

样例

算法1

(模拟+贪心) $O(n^2)$

思路
模拟+贪心，用优先队列维护绝对差，每次取最大的绝对差，插一个数以后再把他放回去，模拟K次，堆顶的绝对差即为所求

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
struct node {
    int l;
    int d;
    node(int l, int d) : l(l), d(d) {}
    node() = default;
    bool operator<(const node b) const {
        int d1 = l / d + (l % d ? 1 : 0);
        int d2 = b.l / b.d + (b.l % b.d ? 1 : 0);
        if (d1 == d2) {
            return d < b.d;
        } else {
            return d1 < d2;
        }
    }
};
priority_queue<node, vector<node>> q;
int main(void) {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        while (!q.empty()) {
            q.pop();
        }
        int n, k;
        int pre, next;
        scanf("%d%d", &n, &k);
        scanf("%d", &pre);
        for (int i = 1; i < n; i++) {
            scanf("%d", &next);
            q.push(node(next - pre, 1));
            pre = next;
        }
        node nod;
        while (k--) {
            nod = q.top();
            q.pop();
            nod.d++;
            q.push(nod);
        }
        nod = q.top();
        int ans = nod.l / nod.d + (nod.l % nod.d ? 1 : 0);
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}