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;
}
updatedupdated2020-05-192020-05-19
加载评论
点击刷新