CodeForces 287B Pipeline(二分)

前端之家收集整理的这篇文章主要介绍了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;
}
原文链接:https://www.f2er.com/javaschema/285963.html

猜你在找的设计模式相关文章