题面描述

在一个虚拟游戏中，塔子哥的目标是将初始等级x提升到更高的等级y（y > x），与n个对手对战。每当他的等级大于或等于对手的等级时，他就获胜并提升1级，反之则降低1级。塔子哥必须选择与对战次数最少的对手进行比赛。任务是计算他达到目标等级y所需的最少对战次数，若无法实现则输出-1。输入包括n、x、y和n个对手的等级，输出为最少对战数。

思路：二分查找 + 贪心

首先，将所有对手的等级进行排序，并计算每个等级与其索引之间的差值。这个差值表示塔子哥在达到这个等级之前需要赢得的比赛数量。

然后，使用二分查找来找到满足条件的最小比赛次数。在每一步，检查当前的比赛次数是否能够使塔子哥的等级达到目标等级。如果可以，就更新答案，并继续在更小的比赛次数中查找。否则，在更大的比赛次数中查找。

在检查当前的比赛次数是否满足条件时，使用贪心的思想。从最低的等级开始，每次选择能够使塔子哥的等级最大提升的比赛。如果当前的比赛次数不足以提升到下一个等级，就停止查找。

最后，输出所需的最少比赛次数。

具体实现

1. 对手等级排序：首先，将所有对手的等级进行排序。这样可以确保塔子哥每次都能以最小的代价与等级较低的对手对战。

2. 计算差值：对于每个对手的等级，我们计算塔子哥当前等级与其等级之间的差值。这个差值代表了塔子哥在达到该等级之前需要赢得的比赛数量。通过这个差值，可以判断塔子哥是否能够在规定的比赛次数内提升自己的等级。

3. 使用二分查找：通过二分查找找到最小的比赛次数。在每一步，检查当前的比赛次数是否能够使塔子哥的等级达到目标等级。如果可以，就更新答案，并继续在更小的比赛次数中查找；否则，转向更大的比赛次数。

4. 贪心策略：在检查比赛次数是否满足条件时，使用贪心的思路。从等级最低的对手开始，每次选择能够使塔子哥的等级最大提升的比赛。这样可以快速累积塔子哥的等级。

5. 输出结果：最后，输出所需的最少比赛次数。如果塔子哥无法达到目标等级，则输出-1。

时间复杂度

$O(nlogn)$

代码

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, cnt = 0; // n是对手数量，cnt用来统计可以直接战胜的对手数量
    long long x, y; // x是塔子哥的初始等级，y是目标等级
    
    vector<long long> nums; // 存储对手的等级
    
    cin >> n >> x >> y; // 输入对手数量、初始等级和目标等级
    
    for (int i = 0; i < n; i++) {
        long long num; // 临时变量，用于读取每个对手的等级
        cin >> num;
        nums.push_back(num); // 将每个对手的等级添加到数组中
    }
    
    sort(nums.begin(), nums.end()); // 对对手等级进行排序
    
    vector<long long> diff(n); // 存储每个对手等级与塔子哥等级之间的差值
    
    for (int i = 0; i < n; i++) {
        diff[i] = max(0LL, nums[i] - i); // 计算当前等级差值
        if (diff[i] <= x) cnt++; // 如果塔子哥能战胜该对手，计数
    }
    
    // 如果当前等级加上可以直接战胜的对手数量 >= 目标等级
    if (x + cnt >= y) {
        cout << y - x << endl; // 输出所需比赛次数
        return 0;
    }
    
    // 如果当前可以战胜的对手数量小于无法战胜的对手数量，输出-1
    if (n - cnt >= cnt) {
        cout << -1 << endl;
        return 0;
    }
    
    long long ans = 0; // 记录总比赛次数
    
    while (x < y) {
        int l = 0, r = n - 1; // 二分查找的左右边界
        while (l < r) {
            int mid = (l + r + 1) / 2; // 计算中间值
            if (diff[mid] <= x) l = mid; // 如果当前等级足够，移动左边界
            else r = mid - 1; // 否则，移动右边界
        }
        
        if (r == n - 1) { // 如果r指向最后一个元素
            cout << ans + y - x << endl; // 输出总比赛次数
            return 0;
        }
        
        r++; // r指向可以战胜的下一个对手
        int cur = 2 * r - n; // 当前能带来的增益
        long long next = min(diff[r], y); // 计算下一个目标等级
        long long d = next - x; // 计算所需的增益
        
        // 如果能达到目标等级，且所需的比赛次数 <= 当前对手数
        if (next == y && d <= r) {
            cout << ans + d << endl; // 输出总比赛次数
            return 0;
        }
        
        // 如果当前可用的增益为负，说明无法提升等级，输出-1
        if (cur < 0) {
            cout << -1 << endl;
            return 0;
        }
        
        // 计算所需的比赛次数
        long long time = d / cur;
        ans += time * n; // 更新总比赛次数
        x += cur * time; // 更新塔子哥的等级
    }
    
    cout << ans << endl; // 输出最终的比赛次数
    return 0;
}

python代码

import bisect  # 导入bisect模块，用于二分查找

# 读取输入并将n、x、y分别赋值，x是初始等级，y是目标等级
[n, x, y] = map(int, input().split())
# 读取对手的等级，排序后存入列表a
a = list(sorted(map(int, input().split())))

# 计算每个对手的等级与其在数组中的索引之间的差值
for i in range(n):
    a[i] = max(0, a[i] - i)  # 将等级减去其索引，确保不小于0

count = 0  # 初始化比赛次数计数
index = 0  # 用于存储当前二分查找的索引

# 只要塔子哥的等级未达到目标等级y，就不断进行循环
while x < y:
    # 使用二分查找找到第一个大于x的对手等级的索引
    index = bisect.bisect(a, x)
    
    # 如果索引等于n，说明所有对手等级都小于等于x
    if index == n:
        count += y - x  # 直接增加到目标等级所需的比赛次数
        break  # 结束循环
    
    base = 2 * index - n  # 计算当前能够提升的基础增益
    target = min(a[index], y)  # 当前目标等级应为a[index]或y的最小值
    diff = target - x  # 计算到达目标等级所需的差值
    
    # 如果目标等级是y，并且差值小于等于当前可用的对手数量
    if target == y and diff <= index:
        count += diff  # 直接增加所需的比赛次数
        break  # 结束循环
    
    # 如果当前的基础增益为负，表示无法进行有效提升
    if base < 0:
        count = -1  # 设置为-1，表示无法达成目标
        break  # 结束循环
    
    # 计算需要的比赛次数，确保整数除法
    t = diff // base
    count += t * n  # 增加总比赛次数
    x += base * t  # 更新塔子哥的等级

# 输出总的比赛次数
print(count)

Java代码

import java.util.*; // 导入Java的集合类和工具类

public class Main {

    public static void main(String[] args) {
        int n, cnt = 0; // n为对手数量，cnt为可以直接战胜的对手计数
        long x, y; // x为塔子哥的初始等级，y为目标等级

        long[] nums; // 存储对手等级的数组

        Scanner in = new Scanner(System.in); // 创建输入扫描器
        n = in.nextInt(); // 读取对手数量
        x = in.nextLong(); // 读取塔子哥的初始等级
        y = in.nextLong(); // 读取塔子哥的目标等级
        nums = new long[n]; // 初始化对手等级数组
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextLong(); // 读取每个对手的等级
        }

        Arrays.sort(nums); // 对对手等级进行排序

        long[] diff = new long[n]; // 用于存储每个对手等级与塔子哥等级之间的差值

        for (int i = 0; i < n; i++) {
            diff[i] = Math.max(0, nums[i] - i); // 计算当前等级差值
            if (diff[i] <= x) cnt++; // 如果塔子哥可以战胜该对手，计数
        }

        // 如果当前等级加上可以直接战胜的对手数量 >= 目标等级
        if (x + cnt >= y) {
            System.out.println(y - x); // 输出所需比赛次数
            return; // 结束程序
        }
        
        // 如果当前可战胜的对手数量小于无法战胜的对手数量，输出-1
        if (n - cnt >= cnt) {
            System.out.println(-1); // 表示无法达到目标等级
            return; // 结束程序
        }

        long ans = 0; // 初始化比赛次数计数
        while (x < y) { // 当塔子哥的等级小于目标等级时继续循环
            int l = 0, r = n - 1; // 二分查找的左右边界
            while (l < r) { // 进行二分查找
                int mid = (l + r + 1) >> 1; // 计算中间值
                if (diff[mid] <= x) l = mid; // 如果当前等级足够，移动左边界
                else r = mid - 1; // 否则，移动右边界
            }

            // 如果r指向最后一个元素，说明塔子哥已经能够战胜所有对手
            if (r == n - 1) {
                System.out.println(ans + y - x); // 输出总比赛次数
                return; // 结束程序
            }

            r++; // r指向可以战胜的下一个对手
            int cur = 2 * r - n; // 当前能带来的增益
            long next = Math.min(diff[r], y); // 计算下一个目标等级
            long d = next - x; // 计算所需的增益
            
            // 如果能达到目标等级，且所需的比赛次数 <= 当前对手数
            if (next == y && d <= r) {
                System.out.println(ans + d); // 输出总比赛次数
                return; // 结束程序
            }

            // 如果当前可用的增益为负，说明无法提升等级，输出-1
            if (cur < 0) {
                System.out.println(-1); // 表示无法达成目标
                return; // 结束程序
            }

            // 计算所需的比赛次数
            long time = d / cur; // 计算可以进行的比赛次数
            ans += time * n; // 更新总比赛次数
            x += cur * time; // 更新塔子哥的等级
        }
        
        System.out.println(ans); // 输出最终的比赛次数
    }
}