这个问题的目标是“最大化”小明(编号为 k)的苹果数。这类“求最大值的最小值”或“求最大值”的问题,如果答案具有单调性,通常可以考虑使用二分查找(二分答案)来解决。
单调性分析: 假设小明最多可以分到 x 个苹果。那么,他一定也可以分到 x−1 个苹果(例如,在 x 的最优方案里,从他的苹果里拿走一个,所有条件仍然满足,只是总苹果数变少了)。反之,如果我们验证出小明无法分到 x 个苹果(即无论怎么分配,总苹果数都会超过 m),那么他也一定无法分到 x+1 个苹果。 因此,小明能分到的苹果数 x 具有单调性,我们可以二分查找这个 x 的最大可能值。
构建 check 函数:
有 t 只苹果,p 名孩子。每位孩子带着号码 1−p ,小明的号码是 w 。分法要尽量公平,号码挨着的孩子拿到的个数相差至多 1 。请问:在号码相邻的孩子所得个数之差不超过 1 这一前提下,怎样让小明拿到的苹果尽量多,并把这个最大值写出来,每个孩子最少也要拿到一只苹果。
首行给出三个整数 p,t,w(1≤p≤t≤109,1≤w≤p) 。
写出一行,代表小明手里那堆苹果的峰值。
输入
5 11 3
输出
3
说明
一种分法是 1 2 3 3 2 。
于是小明手里有 3 只苹果。
© CodeFun2000 · 使用条款
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册