题解 | 环形粒子加速器的能量校准（二分查找法）

核心思想：想象中把前半部分补充到后面，看作连续有序数组来处理。

1. 从断裂点开始依次遍历数组，越界部分求余处理。

#include <iostream>

int main() {
    int n;
    int nums[400];
    int x;
    int offset;  // 断裂点

    std::cin >> n;
    offset = n;
    std::cin >> nums[0];
    for (int i = 1; i < n; i ++) {
        std::cin >> nums[i];
        if (nums[i] < nums[i - 1]) offset = i;  // 标记断裂点
    }
    std::cin >> x;

    for (int i = 0; i < n; i++) {
        int index = (i + offset) % n;  // 越界部分求余处理
        if (nums[index] >= x) {
            offset = index;  // 找到插入位置
            break;
        }
    }

    for (int i = 0; i < offset; i++) {
        std::cout << nums[i] << ' ';
    }
    std::cout << x << ' ';
    for (int i = offset; i < n; i++) {
        std::cout << nums[i] << ' ';
    }
    std::cout << std::endl;

    return 0;
}

2.优化版：既然是有序数组，那就用二分查找来提高效率。

#include <iostream>

// 想象中把前面部分补充到后面，看作连续有序数组即可。
int binary_search(int *nums, int n, int target, int offset) {
    // 注意：需要加上偏移量（对于本身就是有序的数组偏移量为零）
    int left = offset;
    int right = n - 1 + offset;
    while (left < right) {
        int mid = (right + left) / 2;
        if (nums[mid % n] == target) return mid;
        if (nums[mid % n] < target) left = mid + 1;
        else right = mid;
    }
    return right;
}

int main() {
    int n;
    int nums[400];
    int x;
    int offset;  // 断裂点偏移量

    std::cin >> n;
    offset = n;
    std::cin >> nums[0];
    for (int i = 1; i < n; i ++) {
        std::cin >> nums[i];
        if (nums[i] < nums[i - 1]) offset = i;  // 记录断裂点
    }
    std::cin >> x;

    offset = binary_search(nums, n, x, offset) % n;  // 返回的下标还需要求余一次

    for (int i = 0; i < offset; i++) {
        std::cout << nums[i] << ' ';
    }
    std::cout << x << ' ';
    for (int i = offset; i < n; i++) {
        std::cout << nums[i] << ' ';
    }
    std::cout << std::endl;

    return 0;
}