Codeforces1195B Sport Mafia

原题链接：Codeforces1195B

题目大意：初始糖果数为 $0$，两种操作，放糖果与吃糖果，第一次只能放一颗糖果，以后每次要比上一次多放一个，每次只能吃一颗糖果，如果当前没有糖果，则只能选择前一种操作。给定操作次数 $n$ 和终点糖果数 $k$，求吃了多少颗糖果。数据保证有解且唯一。

二分

二分放糖果次数 $[0, n]$，若答案中放糖果次数为 $x$，则 $[0, x]$ 部分最终糖果数都 $≤k$，$(x, n]$ 部分最终糖果数都 $>k$。满足两段性，二分出分界点$x$即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL n, k;

bool check(LL x) {	// 放x次糖果，n-x次吃糖果
	return (x + 1) / 2 * x - (n - x) <= k;
}

int main() {   
	cin >> n >> k;
	LL l = 0, r = n; // 二分放糖果的次数
	while (l < r) {
		LL mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << n - l << endl; 
    return 0;
}

Codeforces1195B Sport Mafia

相关文章：