ACW102
题意
农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N 和 F ，数据间用空格隔开。
接下来 N 行，每行输出一个整数，第i+1行输出的整数代表，第ii片区域内包含的牛的数目。
输出格式
输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。
数据范围
1≤N≤100000 1≤F≤N
输入样例：
1
2
3
4
5
6
7
8
9
10
11
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
1
6500
思路
首先这个题目最暴力的算法是穷举起点和终点,然后算出区间平均值,复杂度O(n^3)
可以用前缀和算区间的和,那么复杂度就是O(n^2),仍然不理想
而且由于是平均值,所以这个选择过程并不能直接对前缀和二分(前缀和大的不一定平均值大,所以无法二分)
对于二分，二分是二分性而不是单调性 只要满足可以找到一个值一半满足一半不满足即可 而不用满足单调性
目前还没有太深刻地理解这句话,
根据这个博客的解释,二分重点不在于单调,而在于想办法筛除一半,
我们把下面的一条定理称之为main theorem： binary search can be used if and only if for all x in S, p(x) implies p(y) for all y > x. 实际上通过这个属性，我们可以将搜索空间减半，也就是说如果我们的问题的解应用这样的一个验证函数，验证函数的值可以满足上述条件，这样这个问题就可以用二分查找的方法来找到那个合适的解，比如最左侧的那个合法解。
从段中就大概明白了,二分可以作为一个验证答案对错的方式来找到答案,只要答案能够满足上述性质.换言之,如果我们二分的对象就是平均值本身,那么一定能让一部分符合一部分不符合,因为假设最优解是avg,那么如果将平均值设置为小于avg,则一定有解 ,这也对应了此博客中的1 1 1 1...... 0 0 0 0.....模型,我们要找的就是最右的1.
所以我们二分平均值,然后对于枚举出来的值进行判断,如果符合,则取右半;如果不符合,则取左半.
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define ll long long
#define LL ll
#define eps 1e-6
using namespace std;
int cow[100100];
double sum[100100];
int n, f;
bool check(double avg) {
sum[0] = 0;
for (int i = 1; i <= n; ++i) { // 求每个值减去平均值的前缀和(只有这样才能符合前缀和的性质)
sum[i] = sum[i - 1] + (cow[i] - avg);
}
double minv = 0;
for (int i = 0, j = f; j <= n; ++i, ++j) { // 枚举起点
minv = min(minv, sum[i]); // i到j的距离是f,取[0,i]中的最小值与sum[j]作差,就能保证区间长度不小于f的都能枚举到
double x = sum[j] - minv;
if (x >= 0) { // 只要有一个区间的平均值大于avg,则avg合法,check()返回1
return 1;
}
}
// 不存在区间平均值大于avg的
return 0;
}
int main() {
while (cin >> n >> f) {
double l = 0;
double r = 0;
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; ++i) {
cin >> cow[i];
r = max(r, 1.0 * cow[i]);
}
while (r - l > eps) { // 模板化写法,这里r,l是浮点数,所以需要控制精度
double mid = (r + l) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
cout << (int) (r * 1000) << endl;
}
return 0;
}
启示
关于二分这里我脑内还是一片混沌,需要多刷一下,是一个盲区
