解题思路

这是一道数学推导题目。根据题目规则：

  1. 个人排成一排，共有 个玩偶
  2. 每个人抢到的玩偶不能比左右两边的人多两个或以上
  3. 第 个位置的人想要赢得游戏

求解步骤：

  1. 假设第 个位置的人抢到 个玩偶
  2. 根据规则，相邻位置的人最少要抢到 个玩偶
  3. 往两边递推，每个位置最少要抢到的玩偶数量会依次减1
  4. 通过数学推导得出最优解公式：

代码

#include <iostream>
using namespace std;

int main() {
    int N, M, k;
    cin >> N >> M >> k;
    
    // 输入验证
    if (N <= 0 || M <= 0 || k <= 0) {
        cout << 0;
        return 0;
    }
    
    // 计算最优解
    int x = (2*M + 2*k*k - 2*k - 2*k*N + N*N + N) / (2*N);
    
    // 验证结果是否有效
    if (x < 0 || x > M) {
        cout << 0;
    } else {
        cout << x;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int k = sc.nextInt();
        
        if (N <= 0 || M <= 0 || k <= 0) {
            System.out.println(0);
            return;
        }
        
        int x = (2*M + 2*k*k - 2*k - 2*k*N + N*N + N) / (2*N);
        
        if (x < 0 || x > M) {
            System.out.println(0);
        } else {
            System.out.println(x);
        }
    }
}

def solve(N: int, M: int, k: int) -> int:
    if N <= 0 or M <= 0 or k <= 0:
        return 0
    
    x = (2*M + 2*k*k - 2*k - 2*k*N + N*N + N) // (2*N)
    
    return x if 0 <= x <= M else 0

N, M, k = map(int, input().split())
print(solve(N, M, k))

算法及复杂度

  • 算法：数学推导
  • 时间复杂度： - 只需要进行简单的数学计算
  • 空间复杂度： - 只使用了常数级别的额外空间