codeforces 1904C

一道很有意思的思维题，需要想到$k$的范围影响，后面处理情况的时候也挺难调的
题目链接

题目大意

给定含有$n$个正整数的数组$a$，有$k$次操作，每次操作中， 选择任意两个数组内不同的存在的元素，并把他们之差的绝对值放入数组中，问$k$次操作后能达到的最小的数组元素为多少

思路

观察样例思考，第一次找出一个值，第二次用第一次的两个数找到同样的值，第三次让两个值相减得$0$，这就是最小值的最优解，所有$k>=3$时，必有唯一最优解$0$，下面只需要讨论$k=1,k=2$的情况了
$k=1$时，$sort$一遍数组，遍历求出相邻元素的最小差值，输出最小差值与数组首元素中较小的那一个
$k=2$时，定义输出值$ans$， 每在求出一对差值后，二分找数组内$>=$这个差值的元素下标，如果合法，比大小更新$ans$

ACcode

#include<bits/stdc++.h>

using ll = long long;

using namespace std;

void solve()
{
    int n, k;cin >> n >> k;
    vector<ll>a(n + 3);
    for (int i = 1;i <= n;i++)cin >> a[i];
    if (k >= 3) {
        cout << 0 << '\n';
        return;
    }
    sort(a.begin() + 1, a.begin() + n + 1);
    if (k == 1) {
        ll ans = a[1];
        for (int i = 2;i <= n;i++)ans = min(ans, a[i] - a[i - 1]);
        cout << ans << '\n';
        return;
    }
    if (k == 2) {
        ll ans = 1e18;
        for (int i = 1;i <= n;i++) {
            for (int j = i + 1;j <= n;j++) {
                ll w = a[j] - a[i];
                ll p = lower_bound(a.begin() + 1, a.begin() + 1 + n, w) - a.begin();
                if (p <= n)ans = min(ans, a[p] - w);
                if (p >= 1)ans = min(ans, w - a[p - 1]);
            }
        }
        cout << ans << '\n';
    }
}

int main() {
    int t;cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}