核心思想：二分答案

这个问题的目标是“最大化”小明（编号为 $k$）的苹果数。这类“求最大值的最小值”或“求最大值”的问题，如果答案具有单调性，通常可以考虑使用二分查找（二分答案）来解决。

1. 单调性分析： 假设小明最多可以分到 $x$ 个苹果。那么，他一定也可以分到 $x-1$ 个苹果（例如，在 $x$ 的最优方案里，从他的苹果里拿走一个，所有条件仍然满足，只是总苹果数变少了）。反之，如果我们验证出小明无法分到 $x$ 个苹果（即无论怎么分配，总苹果数都会超过 $m$），那么他也一定无法分到 $x+1$ 个苹果。 因此，小明能分到的苹果数 $x$ 具有单调性，我们可以二分查找这个 $x$ 的最大可能值。

2. 构建 check 函数： 二分查找的关键是 check(x) 函数，即验证“小明获得 $x$ 个苹果”这个方案是否可行。为了让小明获得 $x$ 个苹果的同时，使用的总苹果数最少，其他小孩的苹果数应该尽可能少。

   • 根据条件2（$|a_i - a_{i+1}| \leq 1$），如果小明（编号 $k$）有 $x$ 个苹果，那么他的邻居（$k-1$ 和 $k+1$）最少可以有 $x-1$ 个苹果。
   • 再往外，编号为 $k-2$ 和 $k+2$ 的小孩最少可以有 $x-2$ 个苹果。
   • 这个数量会以 $k$ 为中心，向两边递减，形成一个“山峰”形状：..., x-2, x-1, x, x-1, x-2, ...
   • 根据条件1，每个小孩至少有 $1$ 个苹果。所以当递减到 $1$ 之后，更远的小孩就不能再少了，只能保持为 $1$。

3. 计算总苹果数： 在 check(x) 函数中，我们需要计算出这种“最节省”的分配方案下，总共需要多少苹果。

   • 小明（编号 $k$）获得 $x$ 个苹果。

   • 左边部分（编号从 $1$ 到 $k-1$）：

     • 从 $k-1$ 到 $1$，与小明的距离依次是 $1, 2, ..., k-1$。
     • 苹果数最少为 $x-1, x-2, ..., 1$。这个递减序列的长度最多为 $x-1$。
     • 设左边有 $L_{kids} = k-1$ 个小孩。
     • 其中，苹果数从 $x-1$ 递减到 $1$ 的小孩数量为 $L = \min(k-1, x-1)$。
     • 这些小孩的苹果总数为一个等差数列的和：$(x-1) + (x-2) + ... + (x-L)$。
     • 剩下 $k-1-L$ 个小孩，他们每人最少分 $1$ 个苹果。
     • 左边总苹果数 sum_left = $\sum_{i=1}^{L}(x-i) + (k-1-L)$。

   • 右边部分（编号从 $k+1$ 到 $n$）：

     • 逻辑与左边完全相同。
     • 设右边有 $R_{kids} = n-k$ 个小孩。
     • 苹果数递减的小孩数量为 $R = \min(n-k, x-1)$。
     • 右边总苹果数 sum_right = $\sum_{i=1}^{R}(x-i) + (n-k-R)$。

   总和公式： 需要的总苹果数 $S(x)$ 为： $S(x) = x + \text{sum\_left} + \text{sum\_right}$ 其中：

   • sum_left = L*x - L*(L+1)/2 + (k-1-L)
   • sum_right = R*x - R*(R+1)/2 + (n-k-R)
   • L = min(k-1, x-1)
   • R = min(n-k, x-1)

代码

C++

#include <iostream>
#include <algorithm>

using namespace std;

// 检查给小明分配 x 个苹果是否可行
// n: 小孩总数, m: 苹果总数, k: 小明编号
bool check(long long x, long long n, long long m, long long k) {
    if (x == 0) return true;
    long long needed = x; // 小明自己需要 x 个

    // 计算左边小孩需要的苹果数
    long long left_kids = k - 1;
    if (left_kids > 0) {
        // 苹果数从 x-1 递减到 1 的小孩数量
        long long l = min(left_kids, x - 1);
        // 等差数列求和 (x-1 + x-l) * l / 2，简化为 l*x - l*(l+1)/2
        needed += l * x - l * (l + 1) / 2;
        // 剩下的小孩每人一个
        if (left_kids > l) {
            needed += (left_kids - l);
        }
    }

    // 计算右边小孩需要的苹果数
    long long right_kids = n - k;
    if (right_kids > 0) {
        // 苹果数从 x-1 递减到 1 的小孩数量
        long long r = min(right_kids, x - 1);
        // 等差数列求和
        needed += r * x - r * (r + 1) / 2;
        // 剩下的小孩每人一个
        if (right_kids > r) {
            needed += (right_kids - r);
        }
    }
    
    return needed <= m;
}

int main() {
    long long n, m, k;
    cin >> n >> m >> k;

    long long low = 1, high = m, ans = 0;

    // 二分查找答案
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, n, m, k)) {
            // 如果 mid 可行，尝试更大的值
            ans = mid;
            low = mid + 1;
        } else {
            // 如果 mid 不可行，需要减小
            high = mid - 1;
        }
    }

    cout << ans << endl;

    return 0;
}

Python

def check(x, n, m, k):
    """
    检查给小明分配 x 个苹果是否可行
    n: 小孩总数, m: 苹果总数, k: 小明编号
    """
    if x == 0:
        return True
    
    needed = x  # 小明自己需要 x 个

    # 计算左边小孩需要的苹果数
    left_kids = k - 1
    if left_kids > 0:
        # 苹果数从 x-1 递减到 1 的小孩数量
        l = min(left_kids, x - 1)
        # 等差数列求和 (x-1 + x-l) * l // 2，简化为 l*x - l*(l+1)//2
        needed += l * x - l * (l + 1) // 2
        # 剩下的小孩每人一个
        if left_kids > l:
            needed += (left_kids - l)

    # 计算右边小孩需要的苹果数
    right_kids = n - k
    if right_kids > 0:
        # 苹果数从 x-1 递减到 1 的小孩数量
        r = min(right_kids, x - 1)
        # 等差数列求和
        needed += r * x - r * (r + 1) // 2
        # 剩下的小孩每人一个
        if right_kids > r:
            needed += (right_kids - r)

    return needed <= m

def solve():
    n, m, k = map(int, input().split())

    low, high = 1, m
    ans = 0

    # 二分查找答案
    while low <= high:
        mid = low + (high - low) // 2
        if mid == 0: # 至少一个苹果
            low = mid + 1
            continue
        
        if check(mid, n, m, k):
            # 如果 mid 可行，尝试更大的值
            ans = mid
            low = mid + 1
        else:
            # 如果 mid 不可行，需要减小
            high = mid - 1

    print(ans)

solve()

Java

import java.util.Scanner;
import java.lang.Math;

public class AppleDistribution {

    // 检查给小明分配 x 个苹果是否可行
    // n: 小孩总数, m: 苹果总数, k: 小明编号
    private static boolean check(long x, long n, long m, long k) {
        if (x == 0) {
            return true;
        }
        long needed = x; // 小明自己需要 x 个

        // 计算左边小孩需要的苹果数
        long leftKids = k - 1;
        if (leftKids > 0) {
            // 苹果数从 x-1 递减到 1 的小孩数量
            long l = Math.min(leftKids, x - 1);
            // 等差数列求和 (x-1 + x-l) * l / 2，简化为 l*x - l*(l+1)/2
            needed += l * x - l * (l + 1) / 2;
            // 剩下的小孩每人一个
            if (leftKids > l) {
                needed += (leftKids - l);
            }
        }

        // 计算右边小孩需要的苹果数
        long rightKids = n - k;
        if (rightKids > 0) {
            // 苹果数从 x-1 递减到 1 的小孩数量
            long r = Math.min(rightKids, x - 1);
            // 等差数列求和
            needed += r * x - r * (r + 1) / 2;
            // 剩下的小孩每人一个
            if (rightKids > r) {
                needed += (rightKids - r);
            }
        }
        
        return needed <= m;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        long k = scanner.nextLong();

        long low = 1, high = m, ans = 0;

        // 二分查找答案
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (mid == 0) { // 至少一个苹果
                low = mid + 1;
                continue;
            }
            if (check(mid, n, m, k)) {
                // 如果 mid 可行，尝试更大的值
                ans = mid;
                low = mid + 1;
            } else {
                // 如果 mid 不可行，需要减小
                high = mid - 1;
            }
        }

        System.out.println(ans);
        scanner.close();
    }
}

题目内容

有 $m$ 个苹果，$n$ 个小孩。每个小孩都有一个编号 $1-n$ ，小明的编号是 $k$ 。要尽量公平的分苹果，相邻编号的小孩分到的苹果数目差距不能大于 $1$ 。请问如何在满足相邻编号的小孩分到的苹果数目差距不能大于 $1$ 的情况下，小明分配到的苹果数目最多，并且输出这个最大值，每个小朋友至少需分配到一个苹果。

输入描述

第一行三个整数 $n,m,k(1≤n≤m≤10^9,1≤k≤n)$ 。

输出描述

输出一行，表示小明分配到苹果个数的最大值。

样例1

输入

4 6 2

输出

2

说明

可以这样分配 $1$ $2$ $2$ $1$ 。

可以小明分配到了 $2$ 个苹果。