题干：
n hobbits are planning to spend the night at Frodo's house. Frodo has n beds standing in a row and m pillows (n ≤ m). Each hobbit needs a bed and at least one pillow to sleep, however, everyone wants as many pillows as possible. Of course, it's not always possible to share pillows equally, but any hobbit gets hurt if he has at least two pillows less than some of his neighbors have.
Frodo will sleep on the k-th bed in the row. What is the maximum number of pillows he can have so that every hobbit has at least one pillow, every pillow is given to some hobbit and no one is hurt?
Input
The only line contain three integers n, m and k (1 ≤ n ≤ m ≤ 109, 1 ≤ k ≤ n) — the number of hobbits, the number of pillows and the number of Frodo's bed.
Output
Print single integer — the maximum number of pillows Frodo can have so that no one is hurt.
Examples
Input
4 6 2
Output
2
Input
3 10 3
Output
4
Input
3 6 1
Output
3
Note
In the first example Frodo can have at most two pillows. In this case, he can give two pillows to the hobbit on the first bed, and one pillow to each of the hobbits on the third and the fourth beds.
In the second example Frodo can take at most four pillows, giving three pillows to each of the others.
In the third example Frodo can take three pillows, giving two pillows to the hobbit in the middle and one pillow to the hobbit on the third bed.
题目大意：
n个人（包括Frodo）在Frodo家里过夜，家里有n张床和m个枕头，每个人都至少一张床和一个枕头，但是每个人都想得到尽可能多的枕头，但是如果有任何一个人的枕头至少比他的邻居少两个，那么就会受伤。（对应那句but any hobbit gets hurt if he has at least two pillows less than some of his neighbors have.）Frodo睡在第k个位置（k<=n）,问：在没有人受伤的情况下，Frodo最多能得到多少个枕头。
解题报告：
这题如果构造的话，情况就太多了，，但是我们可以枚举枕头数啊，因为当主人公的枕头数定下来之后，就很好得到每一次的最优构造了，就是一个简单的数学求和公式了。代码写的很冗长，但是思路很简单。我只是分了情况（在两边和不在两边）。
AC代码：
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
ll n,m,k;
bool ok1(ll x) {
ll res = 0;
if(n < x) res = ((x-n+1) + x) * n / 2;
else res = (1+x)*x/2;
return res <= m;
}
bool ok2(ll x) {
ll res1,res2;
if(k < x) res1 = ((x-k+1)+x)*k/2;
else res1 = (1+x)*x/2;
if(n-k+1 < x) res2 = ((x-(n-k+1)+1)+x)*(n-k+1)/2;
else res2 = (1+x)*x/2;
return res1 + res2 - x <= m;
}
int main()
{
cin>>n>>m>>k;//n人 m枕头 在第k个
if(n == m) {
printf("1");return 0;
}
m=m-n;//默认每个人有一个
ll l = 0,r = m;
ll ans = 0;
ll mid = (l+r)>>1;
if(k == 1 || k == n) {
k=1;
while(l <= r) {
mid = (l+r)>>1;
if(ok1(mid)) {
ans=mid;
l=mid+1;
}
else r=mid-1;
}
}
else {
while(l<=r) {
mid = (l+r)>>1;
if(ok2(mid)) {
ans = mid;
l=mid+1;
}
else r=mid-1;
}
}
printf("%lld\n",ans+1);
return 0 ;
} 总结：
注意一个细节就是ok2函数中构造的时候，中间那条边会被计算两次，举个例子
样例：
4 8 2
应该输出3，结果输出了2。就是因为，x=3的时候，本来用不到m块枕头，但是你重复计算了一次，所以就多算了枕头数，所以就返回了false了、、、
京公网安备 11010502036488号