网站常用代码,flash网站源码模板,临汾哪里有做网站的,新网站seo技术题目
农夫约翰的农场由 N N N 块田地组成#xff0c;每块地里都有一定数量的牛#xff0c;其数量不会少于 1 头#xff0c;也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来#xff0c;并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区…题目
农夫约翰的农场由 N N N 块田地组成每块地里都有一定数量的牛其数量不会少于 1 头也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F F F 块地其中 F F F 会在输入中给出。
在给定条件下计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N N N 和 F F F数据间用空格隔开。
接下来 N N N 行每行输入一个整数第 i 1 i1 i1 行输入的整数代表第 i i i 片区域内包含的牛的数目。
输出格式
输出一个整数表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。
数据范围 1 ≤ N ≤ 100000 1≤N≤100000 1≤N≤100000 1 ≤ F ≤ N 1≤F≤N 1≤F≤N
输入样例
10 6
6
4
2
10
3
8
5
9
4
1输出样例
6500分析
题意简而言之就是给定正整数序列 A A A求一个平均数最大的、长度不小于 L L L 的连续的子段。
二分答案判定 “是否存在一个长度不小于 L L L 的子段平均数不小于二分的值”。
如果把数列中每个数都减去二分的值就转化为判定 “是否存在一个长度不小于 L L L 的子段子段和非负”。
下面着重来解决以下两个问题。 1、求一个子段它的和最大没有 “长度不小于 L L L” 这个限制。 无长度限制的最大子段和问题是一个经典问题只需 O ( N ) O(N) O(N) 扫描该数列不断把新的数加入子段当子段和变成负数时把当前的整个子段清空。扫描过程中出现过的最大子段和即为所求。POJ-1050.To The Max 2、求一个子段它的和最大子段的长度不小于 L L L。 子段和可以转化为前缀和相减的形式即设 s u m i sum_i sumi 表示 A 1 A_1 A1 ~ A i A_i Ai 的和则有 max i − j ≥ L { A j 1 A j 2 . . . A i } max L ≤ i ≤ n { s u m i − min 0 ≤ j ≤ i − L { s u m j } } \max_{\mathclap{i - j \ge L}} \{ A_{j 1} A_{j 2} ... A_i\} \max_{L \le i \le n}\{ sum_i - \min_{0 \le j \le i - L}\{sum_j\}\} i−j≥Lmax{Aj1Aj2...Ai}L≤i≤nmax{sumi−0≤j≤i−Lmin{sumj}}
仔细观察上式可以发现随着 i i i 的增长 j j j 的取值范围 0 ~ i i i - L L L 每次只会增大 1。换言之每次只会有一个新的取值进入 min { s u m j } \min\{sum_j\} min{sumj} 的候选集合所以没有必要每次循环枚举 j j j只需要用一个变量记录当前最小值每次与新的取值 s u m i − L sum_{i-L} sumi−L 取 min \min min 就可以了。
double ans -1e10;
double min_val 1e10;
for (int i L; i N; i) {min_val min(min_val, sum[i - L]);ans max(ans, sum[i] - min_val);
}解决了问题2之后只需要看一下最大子段和是不是非负数就可以确定二分上下界的变化范围了。
本题来源于POJ-2018.Best Cow Fences
代码
#include iostream
using namespace std;const int N 100005;
double a[N], b[N], sum[N];int n, L;bool check(double mid) {for (int i 1; i n; i) b[i] a[i] - mid; //每个数减去二分的值for (int i 1; i n; i) sum[i] sum[i - 1] b[i]; //前缀和double ans -1e10; double min_val 1e10;//子段长度不小于L的最大子段和for (int i L; i n; i) {min_val min(min_val, sum[i - L]);ans max(ans, sum[i] - min_val);}//是否存在一个长度不小于L的子段子段和非负return ans 0;
}int main() {cin n L;for (int i 1; i n; i) scanf(%lf, a[i]);double eps 1e-5;double l -1e6;double r 1e6;while (r - l eps) {double mid (l r) / 2;if (check(mid)) l mid;else r mid;}cout int (r * 1000) endl; return 0;
}
