二分/01分数规划

二分(手搓)

一.找出第一个大于等于 x 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int a[200005];
int main()
{
	int n, x;
	cin >> n >> x;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int z = 1, y = n;
  //核心代码
	while (z <= y)
	{
    //这里其实mid = (z + y) / 2，而下面的写法是为了防止有时候爆int
		int mid = z + (y - z) / 2;
    //下面两个条件判断，哪个不取等，就输出哪个
		if (a[mid] >= x) y = mid - 1;
		else z = mid + 1;
	}
	cout << z; //cout << y + 1;
	return 0;
}

二.找出最后一个小于等于 x 的元素这里只展示核心代码，与一进行比较

1
2
3
4
5
6
7
8
9
10
11
int z = 1, y = n;
  //核心代码
while (z <= y)
{
  //这里其实mid = (z + y) / 2，而下面的写法是为了防止有时候爆int
  int mid = z + (y - z) / 2;
  //下面两个条件判断，哪个不取等，就输出哪个
  if (a[mid] <= x) z = mid + 1;
  else y = mid - 1;
}
cout << y; //cout << z - 1;

简单记忆区分两种情况在于先判断哪种情况

二分(STL)

binary_search 返回 bool 值， 是否存在
lower_bound 返回第一个大于等于 x 元素的地址
upper_bound 返回第一个大于 x 的元素的地址
这三个的参数(a, a + n, x)

答案检验法

一种使用二分思想的方法，给出答案可能的最小值 z ，最大值 y，然后对答案进行二分，假设每次二分的结果就是最后的正确答案，然后循环内部进行 judge 函数判断是否满足，从而进行不同的左右区间缩减。最终找到真正的正确答案。

01 分数规划 的解法就是使用答案检验法

模板题

题解：假设每次二分的答案为 x，现在要验证 x 的正确性
(v1 + v2 + v3 + ……vk) / (w1 + w2 + w3 + ……wk) 是否> x

即 (v1 + v2 + v3 + ……vk) 是否> (w1 + w2 + w3 + ……wk) * x

即(v1 + v2 + v3 + ……vk) - (w1 + w2 + w3 + ……wk) * x 是否> 0

即 (i=1 到 i=k 项的和) vi- x * wi 是否> 0

ac 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
using namespace std;
double y = 0;
int n, k;
struct ty
{
	double w, v;
	double m;
}a[500010];
bool cmp(ty a, ty b)
{
	return a.m > b.m;
}
bool judge(double x)
{
	for (int i = 1; i <= n; i++)
		a[i].m = a[i].v - a[i].w * x;
	sort(a + 1, a + 1 + n, cmp);
	double sum = 0;
	for (int i = 1; i <= k; i++)
		sum += a[i].m;
	if (sum >= 0) return 1;
	return 0;
}
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].w >> a[i].v;
		y += a[i].w;
	}
	double z = 0;
	int t = 100;
	while (t--)
	{
		double mid = (z + y) / 2;
		if (judge(mid)) z = mid;
		else y = mid;
	}
	printf("%.9lf", (z + y) / 2);
	return 0;
}