CodeForces 287B (Pipeline)[二分，贪心]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/287/B

稍加分析，题目可以转换成这样一个问题：给定1, 2, 3, …, k-1, 问它们的部分和是否能凑出n-1，如果能最少要用多少个数。
一种贪心的思想是寻找一个i，使得i, i+1, …, k-1的和大于等于n-1,在这个前提下要求i最大。此时有i+1, i+2, …, k-1的和小于n-1。回想要用最少的数凑出n-1，此时i+1, i+2, …, k-1是一定要选的，对应n-1减去它们的和后所余下的差r一定小于i+1（否则不满足i最大的要求），此时从1, 2, …, i中调出一个数补上即可。
此时对应的所需要的分流器为i+1到k所有分流器和1到i中的某一个分流器。
另外需要注意的是n=1的情况，由于二分没有判断结果是否合理，因此需要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
bool check(ll mid) {
	ll sum=(mid+k-1)*(k-mid)/2;
	return (sum>=n-1);
}
int main() {
	scanf("%I64d%I64d",&n,&k);
	if(n==1) {printf("0");return 0;}
	ll l=1,r=k-1,mid;
	while(l<r) {
		mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	if((l+k-1)*(k-l)/2 >= n-1) printf("%I64d",k-l);
	else printf("-1");
}