CF760B
DDF_
·
·
题解
你好。
题面
分 m 个物品给排成一排的 n 人，求第 k 个人可以拿到的最大物品数，要求相邻的人物品数相差不超过 1，且每个人都有物品。
题解
二分第 k 个人可以拿到的物品数 x。
若第 k 个人拿到 x 个物品，则可以构造出一种方案，使得这一排人拿到的物品数最小。
如果第 i 个人拿到 j 个物品，那么第 i-1 和 i+1 人可以拿到 j-1 或 j 或 j+1 个物品。
由此我们可以这样构造：第 k 个人拿到的最多，然后区间 [k,n] 从 k 到 n 递减，区间 [1,k] 从 k 到 1 递减，当递减到 1 时重复。
显而易见这样构造可以使得拿到物品数最小。
设这个最小值为 s。
然后就可以这样二分了。
时间复杂度 $O(\log m)$。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k;
ll l,r;
bool check(ll x) {
ll b,c;
if(x-(n-k)<=0) b=x*(x-1)/2+1-(x-(n-k));
else b=(x-1+x-(n-k))*(n-k)/2;
if(x-(k-1)<=0) c=x*(x-1)/2+1-(x-(k-1));
else c=(x-1+x-(k-1))*(k-1)/2;
//等差数列求和公式来求[1,k-1]和[k+1,n]贡献
return b+c+x<=m;
}
int main() {
scanf("%lld%lld%lld",&n,&m,&k);
l=1,r=m;
while(l<r) {
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%lld",l);
return 0;
}
```