CodeForces 287B Pipeline（二分）

题目链接：CodeForces 287B Pipeline

题目大意：自来水厂要为n个客户供水，现在有k - 1种分离器，分离器的out口分别为2~k。问说给出n和k，最少需要多少的分离器可以满足所有客户供水，不能满足输出-1。

解题思路：一开始用遍历试了一下，超时了，后来大伙伴告诉我们说二分搜索分两种，其中一种就是二分答案，然后就向着这个方向去做了，结果发现本题的问题不是搜索答案的过程，而是判断当前c个分离器是否可以满足n个用户的供水。

最先是用从计算sum（k-1~k-c的累加和），如果sum>= n的话，c个分离器就能满足条件，但是这样做还是超时了。

后来想想，从k-1 ~ k-c的累加和是一个等差数列的和，可以使用公式（a0+an）*n/2.

#include <iostream>
using namespace std;
long long n;
int k;

bool judge(long c) {
	long long  b = k - c;
	long long sum = (b + k - 1) * c / 2 + 1;
	return sum >= n;
}

int search() {
	if (!judge(k - 1)) return -1;
	if (judge(0))	   return 0;
	int l = 0,r = k - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (judge(mid)) r = mid;
		else l = mid;

		if (l == r - 1) return r;
	}
}

int main () {
	cin >> n >> k;
	cout << search() << endl;
	return 0;
}

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!