Codeforces 760B：Frodo and pillows（二分）

http://codeforces.com/problemset/problem/760/B

题意：有n张床m个枕头，每张床可以有多个枕头，但是相邻的床的枕头数相差不能超过1，问第k张床最多能拥有的枕头数是多少。每张床至少有一个枕头。

思路：因为每张床至少需要一个枕头，所以先将m减掉n之后来考虑剩余枕头如何分配。

我们考虑一个最优的情况，假设有5张床，9个枕头，k为3的时候，那么这样分配：1 2 3 2 1，这样其实就如同阶梯一样，要让第k个最高，然后向两边递减。

我们可以二分答案，使用等差数列的公式来做，数出分配在k左边需要的枕头数，还有k右边需要分配的枕头数，然后判断剩余的枕头数是否满足需要分配的枕头数。

有一些细节需要考虑：例如上面这个样例，当我们枚举分配给k的枕头数为1的时候，是这样分配的：0 0 1 0 0。即枚举的枕头数比左边（或者右边）的床数要少，这个时候要特殊考虑一下。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 3010
 4 #define INF 0x3f3f3f3f
 5 typedef long long LL;
 6 
 7 LL cal(LL a, LL n) { // 等差求和公式
 8     return a * n + n * (n - 1) / 2;
 9 }
10 
11 int main() {
12     LL n, m, k;
13     cin >> n >> m >> k;
14     m -= n;
15     LL lcnt = k - 1, rcnt = n - k, l = 0, r = m, ans = 0;
16     while(l <= r) {
17         LL mid = (l + r) >> 1;
18         LL tmp = mid;
19         LL left, right;
20         if(mid - lcnt < 1) { // 枚举的枕头数比左边的床数要少
21             left = cal(1, mid - 1); // 从1开始,数量为枚举的枕头数-1
22         } else left = cal(mid - lcnt, lcnt);
23         if(mid - rcnt < 1) { // 同理
24             right = cal(1LL, mid - 1);
25         } else right = cal(mid - rcnt, rcnt);
26         tmp += left + right;
27         if(tmp > m) r = mid - 1;
28         else { ans = mid; l = mid + 1; }
29     }
30     cout << ans + 1 <<endl; // 因为一开始已经每个床分配了一个枕头,所以要加回1
31     return 0;
32 }