Codeforces 760B. Frodo and pillows题目描述有mmm个苹果nnn个小孩。每个小孩都有一个编号1−n1-n1−n小明的编号是kkk。要尽量公平的分苹果**相邻编号的小孩分到的苹果数目差距不能大于111。**请问如何在满足相邻编号的小孩分到的苹果数目差距不能大于111的情况下小明分配到的苹果数目最多并且输出这个最大值每个小朋友至少需分配到一个苹果。输入第一行三个整数n,m,k(1n≤m≤109,1k≤n)n,m,k(1 \lt n \le m \le 10^9,1k≤n)n,m,k(1n≤m≤109,1k≤n)。输出输出一行表示小明分配到苹果个数的最大值。数学描述输入nnnm(1≤n≤m≤109)m(1 \le n \le m \le 10^9)m(1≤n≤m≤109)k(1≤k≤n)k(1 \le k \le n)k(1≤k≤n)。现在有一个长度nnn的数组aaa已知其所有元素均为正整数元素和为mmm并且∣a[i]−a[i1]≤1∣|a[i] - a[i1] \le 1|∣a[i]−a[i1]≤1∣。问a[k]a[k]a[k]最大能是多少样例 1输入4 6 5输出2样例 2输入3 10 3输出4样例 3输入3 6 1输出3思路这个题比较容易发现单调性因为a[k]a[k]a[k]越大整个数组的元素之和越大所以能用二分答案来做。对于某个给定的a[k]a[k]a[k]值我们将其视为整个数组的峰值从它开始向数组的两翼递减可以得到最优解。复杂度分析时间复杂度在值域范围[1,m][1,m][1,m]内进行二分答案check是 O(1) 的因此时间复杂度为O(log2m)O(log_2^m)O(log2m​)。空间复杂度整个算法过程仅使用了有限几个变量因此额外空间复杂度为O(1)O(1)O(1)。C 代码#includeiostream#includealgorithmusingnamespacestd;usingLLlonglong;intn,m,k;// 错误的做法check 的时间复杂度为 O(N)boolwrong_check(intmid){LL summid;for(intik1,tmid-1;in;i)summax(1,t--);for(intik-1,tmid-1;i1;i--)summax(1,t--);returnsumm;}// 正确的做法通过数学公式O(1) 时间内计算出 sum// 以 LL接受参数避免后续计算乘法爆 intLLget(LL len,LL mid){if(lenmid){// [mid - len 1, mid]// sum (a1 an) * len / 2return(mid-len1mid)*len/2;}// [1, ... 1, 2, ... mid]return(len-mid)(1mid)*mid/2;}// 正确的做法check 的时间复杂度为 O(1)boolcheck(LL mid){// [1,k-1], [k1,n]LL summid;sumget(k-1,mid-1);sumget(n-k,mid-1);returnsumm;}intmain(){cinnmk;LL l1,rm;while(lr){LL mid(lr1)/2;if(check(mid))lmid;elsermid-1;}coutlendl;return0;}参考资料https://codeforces.com/problemset/problem/760/Bhttps://www.acwing.com/solution/content/244862/?utm_sourcechatgpt.com