题解 | #环形粒子加速器的能量校准#

题目链接

题目描述

在一个先进的环形粒子加速器中，科学家们需要精确控制其中粒子的能量分布。加速器环道上分布着 $n$ 个等距的能量监测点，能量值序列为 $e$ 。

为了维持磁场稳定，该序列 $e$ 必须满足“循环单调非递减”性质：序列中至多存在一个“断点”下标 $i$ ，使得 $e_i > e_{(i+1) \pmod n}$ ，而在所有其他位置 $j$ ，均满足 $e_j \le e_{j+1}$ 。

现在，需要向加速器中注入一个能量值为 $x$ 的新粒子。任务是，找到一个合适的插入位置，将 $x$ 插入序列 $e$ 中，形成一个长度为 $n+1$ 的新序列 $e'$ ，并确保 $e'$ 仍然满足“循环单调非递减”性质。

如果存在多个合法插入位置，请选择使得新粒子在 $e'$ 中下标最小的那个位置。

解题思路

题目的核心要求是在一个满足“循环单调非递减”性质的数组中插入一个新元素，并保持该性质。同时，如果存在多个合法的插入位置，需要选择新元素下标最小的那个。

“循环单调非递减”的序列本质上是一个被旋转过的非递减序列。例如，序列 [4, 5, 1, 2, 3] 就是 [1, 2, 3, 4, 5] 旋转得到的。

考虑到数据规模 $n \le 50$ ，我们可以采用一个直接且清晰的模拟思路：

遍历所有可能的插入位置：从下标 $0$ 到 $n$ (包含 $n$ ) 遍历，尝试将新粒子 $x$ 插入到每一个可能的位置。
构建临时序列：对于每个插入位置 $i$ ，我们构建一个新的、长度为 $n+1$ 的临时序列。
验证性质：编写一个辅助函数，检查这个临时序列是否满足“循环单调非递减”性质。
- 验证方法是：遍历新序列，统计其中满足 $e'_j > e'_{j+1}$ (对于环形序列，最后一个元素与第一个元素也需要比较) 的“断点”数量。
- 如果断点数量小于或等于 1，那么该序列就满足性质。
寻找最优解：由于我们是从小到大遍历插入位置的，第一个使得临时序列满足性质的位置，就是新粒子 $x$ 下标最小的合法位置。此时，直接输出这个临时序列并结束程序即可。

这种方法虽然时间复杂度是 $\mathcal{O}(n^2)$ ，但对于本题的数据范围来说完全足够，并且逻辑简单，不易出错。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// 检查序列是否满足循环单调非递减性质
bool is_valid(const vector<long long>& arr) {
    int n = arr.size();
    if (n <= 1) {
        return true;
    }
    int break_points = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            break_points++;
        }
    }
    if (arr[n - 1] > arr[0]) {
        break_points++;
    }
    return break_points <= 1;
}

int main() {
    int n;
    cin >> n;
    vector<long long> e(n);
    for (int i = 0; i < n; ++i) {
        cin >> e[i];
    }
    long long x;
    cin >> x;

    for (int i = 0; i <= n; ++i) {
        vector<long long> temp_e = e;
        temp_e.insert(temp_e.begin() + i, x);
        if (is_valid(temp_e)) {
            for (int j = 0; j < temp_e.size(); ++j) {
                cout << temp_e[j] << (j == temp_e.size() - 1 ? "" : " ");
            }
            cout << endl;
            return 0;
        }
    }

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    // 检查序列是否满足循环单调非递减性质
    private static boolean isValid(List<Long> arr) {
        int n = arr.size();
        if (n <= 1) {
            return true;
        }
        int breakPoints = 0;
        for (int i = 0; i < n - 1; i++) {
            if (arr.get(i) > arr.get(i + 1)) {
                breakPoints++;
            }
        }
        if (arr.get(n - 1) > arr.get(0)) {
            breakPoints++;
        }
        return breakPoints <= 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> e = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            e.add(sc.nextLong());
        }
        long x = sc.nextLong();

        for (int i = 0; i <= n; i++) {
            List<Long> tempE = new ArrayList<>(e);
            tempE.add(i, x);
            if (isValid(tempE)) {
                for (int j = 0; j < tempE.size(); j++) {
                    System.out.print(tempE.get(j) + (j == tempE.size() - 1 ? "" : " "));
                }
                System.out.println();
                return;
            }
        }
    }
}

# 检查序列是否满足循环单调非递减性质
def is_valid(arr):
    n = len(arr)
    if n <= 1:
        return True
    break_points = 0
    for i in range(n - 1):
        if arr[i] > arr[i+1]:
            break_points += 1
    if arr[n-1] > arr[0]:
        break_points += 1
    return break_points <= 1

def main():
    n = int(input())
    e = list(map(int, input().split()))
    x = int(input())

    for i in range(n + 1):
        temp_e = e[:i] + [x] + e[i:]
        if is_valid(temp_e):
            print(*temp_e)
            return

if __name__ == "__main__":
    main()

算法及复杂度

算法：模拟。通过遍历所有可能的插入点，并逐一验证生成的新序列是否满足题目要求，来找到最小下标的合法插入位置。
时间复杂度： $\mathcal{O}(n^2)$ 。外层循环遍历 $n+1$ 个可能的插入位置。对于每个位置，插入操作需要 $\mathcal{O}(n)$ ，验证性质也需要 $\mathcal{O}(n)$ 。因此总时间复杂度为 $\mathcal{O}(n \cdot (n+n)) = \mathcal{O}(n^2)$ 。
空间复杂度： $\mathcal{O}(n)$ 。每次循环都需要创建一个长度为 $n+1$ 的临时数组来存储插入新粒子后的序列。