题目链接
皇家翻译
输入n，m，k，n代表有n个床，m代表有m个枕头，你在第k个床位。现在每个床位至少要有一个枕头，并且相邻两个床位之间的枕头差不能超过1，最后输出你能得到的最多枕头数。
初步思路
显然在你床位两侧的枕头的分配规律是公差为一的等差数列。如果从正面出发，我们可以分四种情况 PS（当k=1或者k=n时当前床位就是最左侧或最右侧床位，此时只用考虑另一侧床位的枕头排列即可）
床位左侧的等差数列的首项（最左侧床位）是>1的，床位右侧的等差数列的首项（最右侧床位）也是>1的。床位左侧的等差数列的首项（最左侧床位）是>1的，床位右侧的等差数列的首项（最右侧床位）是=1的。床位左侧的等差数列的首项（最左侧床位）是=1的，床位右侧的等差数列的首项（最右侧床位）也是>1的。床位左侧的等差数列的首项（最左侧床位）是=1的，床位右侧的等差数列的首项（最右侧床位）是=1的。
那我们可以根据等差数列的性质进行求解，但是这样的计算过程有些繁琐，我们可以反向 操作一波。
改进方法
如果我们知道答案的话，其实结果是很好判断的，因为当前位置的枕头数量已经知道了，我们只要根据等差数列的性质去推出左右两侧需要多少枕头，然后在判断一下当前的枕头数量是否能满足这个需求。于是我们可以二分答案，然后去判断答案是否可行就好了。
上代码！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define piii pair<pii, int>
#define uf(a, b, i) for (register int i = (a); i <= (b); ++i)
#define df(a, b, i) for (register int i = (a); i >= (b); --i)
using namespace std
;
inline int read() {
int x
= 0, f
= 1;
char ch
= getchar();
while(ch
< '0' || ch
> '9') {
if(ch
== '-') f
= -1;
ch
= getchar();
}
while(ch
>= '0' && ch
<= '9') {
x
= x
* 10 + ch
- '0';
ch
= getchar();
}
return x
* f
;
}
template<class T>
inline void print(T x
) {
if(x
> 9) print(x
/10);
putchar(x
%10 + '0');
}
template<class T>
void Swap(T
&a
, T
&b
) {
T temp
= a
;
a
= b
;
b
= temp
;
}
template<class T>
T
Max(T a
, T b
) {
return a
> b
? a
: b
;
}
template<class T>
T
Min(T a
, T b
) {
return a
< b
? a
: b
;
}
const ll mod
= 1e9 + 7;
int n
, m
, k
, a
, b
, ans
;
bool jdg(int x
) {
ll sum
= x
;
if (x
>= a
) {
sum
+= 1ll*a
*(a
+1)/2 + 1ll*a
*(x
-a
-1);
} else {
sum
+= 1ll*x
*(x
-1)/2;
}
if (x
>= b
) {
sum
+= 1ll*b
*(b
+1)/2 + 1ll*b
*(x
-b
-1);
} else {
sum
+= 1ll*x
*(x
-1)/2;
}
return sum
<= m
;
}
void scan() {
n
= read(); m
= read(); k
= read();
}
void work() {
m
-= n
; a
= k
- 1; b
= n
- k
;
int l
= 0, r
= m
, mid
;
while (l
<= r
) {
mid
= l
+ r
>> 1;
if (jdg(mid
)) ans
= mid
, l
= mid
+ 1;
else r
= mid
- 1;
}
print(ans
+1);
putchar('\n');
}
int main() {
scan();
work();
return 0;
}
