题解 | #疯狂队列#
疯狂队列
https://www.nowcoder.com/practice/d996665fbd5e41f89c8d280f84968ee1
解题思路
- 首先将所有学生身高降序排序
- 初始取最大值和最小值，计算它们的差值
- 使用两个指针分别指向次大值和次小值的位置
- 依次计算最大值与次小值的差值，以及次大值与最小值的差值
- 更新最大值和最小值，继续计算直到两个指针相遇
- 最后处理剩余的一个差值
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> h;
for(int i = 0; i < n; i++) {
int x;
cin >> x;
h.push_back(x);
}
sort(h.begin(), h.end(), greater<int>());
int max = h[0];
int min = h[n-1];
int maxIdx = 1;
int minIdx = n-2;
int sum = max - min;
while(minIdx > maxIdx) {
sum += max - h[minIdx] + h[maxIdx] - min;
max = h[maxIdx++];
min = h[minIdx--];
}
if(minIdx == maxIdx) {
sum += max - h[minIdx] > h[maxIdx] - min ?
max - h[minIdx] : h[maxIdx] - min;
}
cout << sum << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Integer[] h = new Integer[n];
for(int i = 0; i < n; i++) {
h[i] = sc.nextInt();
}
Arrays.sort(h, Collections.reverseOrder());
int max = h[0];
int min = h[n-1];
int maxIdx = 1;
int minIdx = n-2;
int sum = max - min;
while(minIdx > maxIdx) {
sum += max - h[minIdx] + h[maxIdx] - min;
max = h[maxIdx++];
min = h[minIdx--];
}
if(minIdx == maxIdx) {
sum += Math.max(max - h[minIdx], h[maxIdx] - min);
}
System.out.println(sum);
}
}
n = int(input())
h = list(map(int, input().split()))
h.sort(reverse=True)
max_val = h[0]
min_val = h[n-1]
max_idx = 1
min_idx = n-2
sum_val = max_val - min_val
while min_idx > max_idx:
sum_val += max_val - h[min_idx] + h[max_idx] - min_val
max_val = h[max_idx]
min_val = h[min_idx]
max_idx += 1
min_idx -= 1
if min_idx == max_idx:
sum_val += max(max_val - h[min_idx], h[max_idx] - min_val)
print(sum_val)
算法及复杂度
- 算法：贪心算法
- 时间复杂度：
- 主要来自排序
- 空间复杂度：
- 需要存储输入数组
查看4道真题和解析
OPPO成长空间 954人发布