解题思路

为了在相邻编号差值不超过 1且每人至少 1 个的前提下让小明（位置 $k$ ）拿到尽可能多的苹果，最优分配的形状必然是以位置 $k$ 为“峰顶”的坡度为 1 的山形：位置 $i$ 处的苹果最少为 $\max(x-|i-k|,\,1)$ ，其中 $x$ 是小明拿到的数量。这样在给定 $x$ 时，其它人被压到最低合法值，使得总和最小，从而检验该 $x$ 是否可行。
相关算法：二分答案 + 数学求和/贪心构造的可行性判定。
具体做法：
1. 设串长为 $n$ 、总苹果 $m$ 、小明在 $k$ 。令左侧人数 $L=k-1$ 、右侧人数 $R=n-k$ 。
2. 给定候选峰值 $x$ 时，最小总和为

P3833.第3题-分苹果

1000ms

Difficulty: 5

所属公司 : 网易

算法与标签>二分算法

有 $m$ 个苹果， $n$ 个小孩。每个小孩都有一个编号 $1-n$ ，小明的编号是 $k$ 。要尽量公平的分苹果，相邻编号的小孩分到的苹果数目差距不能大于 $1$ 。

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

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

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

输入

4 6 2

输出

说明

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

输入

预期输出（选填）