环形粒子加速器的能量校准

题意

给定一个长度为 $n$ 的整数序列，它满足"循环单调非递减"性质：在环形意义下，至多存在一个断点位置 $i$ ，使得 $e_i > e_{i+1}$ （下标取模），其余相邻对都满足 $e_j \le e_{j+1}$ 。

现在要把一个新能量值 $x$ 插入序列，使得新序列仍然满足这个性质。如果有多个合法位置，选下标最小的。

思路

先搞清楚"循环单调非递减"到底是什么。你可以把序列想象成一个环，沿着环走一圈，最多只能有一个地方是"下降"的。比如 [23, 37, 39, 49, 49, 16, 22]，从 49 到 16 有一个下降，其他都是非递减的——这就像一个排好序的数组被旋转了一下。

那插入 $x$ 之后会发生什么？关键观察是：插入操作只影响局部。

假设我们把 $x$ 插到位置 $p$ （0-indexed），新序列变成 $e[0..p-1], x, e[p..n-1]$ 。这个操作：

断开了原来 $e[p-1]$ 和 $e[p]$ 之间的相邻关系
新增了 $(e[p-1], x)$ 和 $(x, e[p])$ 这两对相邻关系

所以新序列的断点数 = 原来的断点数 - 被断开的那对是否是断点 + 新增的两对中有几个是断点。

用公式写就是：

$ $\text{newBP} = \text{bpCount} - [e[p-1] > e[p]] + [e[p-1] > x] + [x > e[p]]$ $

（边界情况： $p=0$ 或 $p=n$ 时断开的是环形边 $(e[n-1], e[0])$ 。而且这两个位置断开的是同一条边，所以 $p=0$ 和 $p=n$ 的断点数算出来一样，我们只需要考虑 $p=0$ 就行。）

只要 $\text{newBP} \le 1$ 就合法。从 $p=0$ 开始扫到 $p=n$ ，第一个合法的就是答案。

复杂度

预处理断点数： $O(n)$
枚举插入位置： $O(n)$
总体 $O(n)$

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    vector<int> e(n);
    for(int i=0;i<n;i++) scanf("%d",&e[i]);
    int x;
    scanf("%d",&x);

    if(n==0){
        printf("%d\n",x);
        return 0;
    }

    int bpCount = 0;
    for(int i=0;i<n;i++){
        if(e[i] > e[(i+1)%n]) bpCount++;
    }

    int best = -1;
    for(int p=0; p<=n; p++){
        int lv, rv, rem;
        if(p==0 || p==n){
            lv = e[n-1]; rv = e[0];
            rem = (e[n-1]>e[0]) ? 1 : 0;
        } else {
            lv = e[p-1]; rv = e[p];
            rem = (e[p-1]>e[p]) ? 1 : 0;
        }
        int nb = bpCount - rem + (lv>x?1:0) + (x>rv?1:0);
        if(nb <= 1){ best = p; break; }
    }

    for(int i=0;i<best;i++){
        if(i) printf(" ");
        printf("%d",e[i]);
    }
    if(best>0) printf(" ");
    printf("%d",x);
    for(int i=best;i<n;i++) printf(" %d",e[i]);
    printf("\n");
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] e = new int[n];
        for (int i = 0; i < n; i++) e[i] = sc.nextInt();
        int x = sc.nextInt();

        if (n == 0) {
            System.out.println(x);
            return;
        }

        int bpCount = 0;
        for (int i = 0; i < n; i++) {
            if (e[i] > e[(i + 1) % n]) bpCount++;
        }

        int best = -1;
        for (int p = 0; p <= n; p++) {
            int lv, rv, rem;
            if (p == 0 || p == n) {
                lv = e[n - 1]; rv = e[0];
                rem = (e[n - 1] > e[0]) ? 1 : 0;
            } else {
                lv = e[p - 1]; rv = e[p];
                rem = (e[p - 1] > e[p]) ? 1 : 0;
            }
            int nb = bpCount - rem + (lv > x ? 1 : 0) + (x > rv ? 1 : 0);
            if (nb <= 1) { best = p; break; }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < best; i++) {
            if (i > 0) sb.append(' ');
            sb.append(e[i]);
        }
        if (best > 0) sb.append(' ');
        sb.append(x);
        for (int i = best; i < n; i++) sb.append(' ').append(e[i]);
        System.out.println(sb);
    }
}

import sys
input = sys.stdin.readline

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

if n == 0:
    print(x)
else:
    bp_count = sum(1 for i in range(n) if e[i] > e[(i+1) % n])

    best = -1
    for p in range(n + 1):
        if p == 0 or p == n:
            lv, rv = e[n-1], e[0]
            rem = 1 if e[n-1] > e[0] else 0
        else:
            lv, rv = e[p-1], e[p]
            rem = 1 if e[p-1] > e[p] else 0
        nb = bp_count - rem + (1 if lv > x else 0) + (1 if x > rv else 0)
        if nb <= 1:
            best = p
            break

    result = e[:best] + [x] + e[best:]
    print(' '.join(map(str, result)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const e = lines[1].split(' ').map(Number);
    const x = parseInt(lines[2]);

    if (n === 0) {
        console.log(x);
        return;
    }

    let bpCount = 0;
    for (let i = 0; i < n; i++) {
        if (e[i] > e[(i + 1) % n]) bpCount++;
    }

    let best = -1;
    for (let p = 0; p <= n; p++) {
        let lv, rv, rem;
        if (p === 0 || p === n) {
            lv = e[n - 1]; rv = e[0];
            rem = (e[n - 1] > e[0]) ? 1 : 0;
        } else {
            lv = e[p - 1]; rv = e[p];
            rem = (e[p - 1] > e[p]) ? 1 : 0;
        }
        const nb = bpCount - rem + (lv > x ? 1 : 0) + (x > rv ? 1 : 0);
        if (nb <= 1) { best = p; break; }
    }

    const result = [...e.slice(0, best), x, ...e.slice(best)];
    console.log(result.join(' '));
});