二分模板

时间：2019-02-16 21:05:36 阅读：160 评论：0 收藏：0 [点我收藏+]

模板1：满足条件的最大值（最大的最小值）

int erf(int le, int ri) {//求满足条件的最大值
	while (le + 1 <ri) {//防止死循环
		int mid = le + ri >> 1;// ‘+‘优先级大于‘>>‘
		if (check(mid))//check()函数：mid满足条件
			le = mid;
		else
			ri = mid;
	}
	return le;
}

模板2：满足条件的最小值（最小的最大值）

int erf(int le, int ri) {//求满足条件的最小值
	while (le + 1 <ri) {//防止死循环
		int mid = le + ri >> 1;// ‘+‘优先级大于‘>>‘
		if (check(mid))//check()函数：mid满足条件
			ri = mid;
		else
			le = mid;
	}
	return ri;
}

　　模板1例题：

Aggressive cows：二分+贪心

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don‘t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

* Line 1: One integer: the largest minimum distance

Sample Input

Sample Output

Hint

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

题目大意： n个牛棚安排c个牛，求这c头牛两头之间的在最优的方案下，最大的距离

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n, c, a[100010];

int read() {
	int noo1 = 0, noo2 = 1;
	char ch = getchar();
	while (ch<‘0‘ || ch>‘9‘) { if (ch == ‘-‘)noo2 = -1; ch = getchar(); }
	while (ch >= ‘0‘&&ch <= ‘9‘) noo1 = noo1 * 10 + ch - ‘0‘, ch = getchar();
	return noo1*noo2;
}

int check(int x) {
	int cnt = 1,ans=a[0];//ans记录上一个安排的牛棚
	for (int i = 1; i < n; i++) {
		if (a[i] - ans >= x) {
			cnt++;
			ans = a[i];
		}
		if (cnt >= c)//如果满足条件，能安排下
			return 1;
	}
	return 0;//不能安排下
}

int main() {
	cin >> n >> c;
	for (int i = 0; i < n; i++)
		a[i]=read();

	sort(a, a + n);//二分前提：单调性

	int le = 0, r = a[n-1]-a[0];//确定边界
	while (le+1 <r) {
		int mid = le + r >> 1;
		if (check(mid))//满足条件，向大找，看看比当前大还有没有满足的
			le = mid;
		else 
			r = mid;	
	}
	cout << le << "\n";
	return 0;
}

二分模板

原文：https://www.cnblogs.com/52dxer/p/10389166.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)