Codeforces题解｜1537C - Challenging Cliffs

题目信息 📚

【题目描述】

You are a game designer and want to make an obstacle course. The player will walk from left to right. You have $n$ heights of mountains already selected and want to arrange them so that the absolute difference of the heights of the first and last mountains is as small as possible.

In addition, you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains $i$ $(1 \leq i < n)$ such that $h_i \leq h_{i+1}$ where $h_i$ is the height of the $i$-th mountain. You don’t want to waste any of the mountains you modeled, so you have to use all of them.

From all the arrangements that minimize $|h_1 - h_n|$, find one that is the most difficult. If there are multiple orders that satisfy these requirements, you may find any.

【输入】

The first line will contain a single integer $t$ $(1 \leq t \leq 100)$ — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ $(2 \leq n \leq 2 \times 10^5)$ — the number of mountains.

The second line of each test case contains $n$ integers $h_1, \ldots, h_n$ $(1 \leq h_i \leq 10^9)$, where $h_i$ is the height of the $i$-th mountain.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

【输出】

For each test case, output $n$ integers — the given heights in an order that maximizes the difficulty score among all orders that minimize $|h_1 - h_n|$.

If there are multiple orders that satisfy these requirements, you may output any.

【输入样例1】

【输出样例1】

2 4 1 2 
1 3

【提示】

In the first test case:

The player begins at height 2, next going up to height 4, increasing the difficulty by 1. After that, he will go down to height 1, and the difficulty doesn’t change because he is going downhill. Finally, the player will go up to height 2, and the difficulty will increase by 1. The absolute difference between the starting height and the end height is equal to 0, and it’s minimal. The difficulty is maximal.

In the second test case:

The player begins at height 1, next going up to height 3, increasing the difficulty by 1. The absolute difference between the starting height and the end height is equal to 2, and it’s minimal as they are the only heights. The difficulty is maximal.

【题目来源】

https://codeforces.com/problemset/problem/1537/C

题目解析 🍉

【题目分析】

思维题。

首先对所有高度从小到大排序，绝对值相差最小的两个数在排序后会处于相邻位置。

假设高度为 a < b < c < d < e < f < g（且 c 和 d 的绝对值差值最小），则最佳的排列顺序为：d e f g / a b c

PS：当 n = 2 时，排序顺序应当为：c d

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, tmp;

void solve() {
    // 读入高度并且排序
    cin >> n;
    vector<int> a;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        a.push_back(tmp);
    }
    sort(a.begin(), a.end());

    // 输出符合要求的排列
    if (n == 2) cout << a[0] << " " << a[1] << endl;
    else {
        // 寻找绝对值相差最小的下标
        int res = INT_MAX, id = -1;
        for (int i = 0; i < a.size() - 1; i++) {
            int dis = abs(a[i + 1] - a[i]);
            if (dis < res) {
                res = dis, id = i;
            }
        }

        // 输出最佳排列
        for (int i = id + 1; i < a.size(); i++)
            cout << a[i] << " ";
        for (int i = 0; i <= id; i++)
            cout << a[i] << " ";
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}