CF1734A Select Three Sticks 题解

YH_Eternally · 2022-10-13 09:18:00 · 题解

题意

给你一堆木棍，每次选择一根棍子，然后增加或减少它的长度 1。每次操作后，所有杆的长度都应为正。

求从 n 根木棒中选出 3 根并在不折断的情况下使用它们来形成一个等边三角形的最小操作次数。

思路

将木棍从小到大排序，这样就保证了连续 3 个木棍之间的差距最小，再从第 1 根木棍枚举到最后一根木棍，每次选取三根木棍，取他们的差值最小值，即可计算出答案。

代码

#include <bits/stdc++.h>

using namespace std;

int a[500], s[500], ans;

int main() {
    int t, n;
    scanf("%d", &t);
    while(t --) {
        ans = 0x3f3f3f3f;
        memset(a, 0, sizeof(a));
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        for(int i = 2; i <= n - 1; i ++) {
            s[i] = abs(a[i - 1] - a[i]) + abs(a[i + 1] - a[i]);//取差值
            ans = min(ans, s[i]);//取最小值
        }
        cout << ans << endl;
    }
    return 0;
}