2524 双节棍
小于 1 分钟
2524 双节棍
【算法】 排序、贪心
【C++】 sort、数组
【难度】 入门
一、题目简述
有 根双节棍(),第 根长度为 。要选两根,使得长度差尽可能小,输出最小差值。
二、解题思路
先对长度数组排序。排序后,相邻两根的长度差一定是最小的候选值之一。
直观理解:如果选不相邻的两根,它们之间一定有相邻的棍子,差值不会比相邻的更小。
所以只需排序后遍历相邻元素,求最小差值即可。
手动模拟:[3, 4, 1, 6, 8]
- 排序后:
[1, 3, 4, 6, 8] - 相邻差:3-1=2, 4-3=1, 6-4=2, 8-6=2
- 最小差 = 1
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[105];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int minDiff = a[1] - a[0];
for (int i = 1; i < n - 1; i++) {
minDiff = min(minDiff, a[i + 1] - a[i]);
}
cout << minDiff << endl;
return 0;
}四、复杂度分析
- 时间:,排序开销。,瞬间完成。
- 空间:。
