题目描述
农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N 和 F ，数据间用空格隔开。
接下来 N 行，每行输出一个整数，第i+1行输出的整数代表，第i片区域内包含的牛的数目。
输出格式
输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。
数据范围
1≤N≤100000
1≤F≤N
输入样例：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
6500
算法 前缀和+DP
使用DP，dp[i], 表示第 dp[i] 个位置到 第 i 个位置的最优。(dp[i], i].例如 dp[9] = 3, 是表示(3, 9]也就就是，4~9，6个数的最优。那么对于 第 i 个位置来说，有两种情况 要么根据第 i - 1 个位置的最优推导，要么自己和前 k - 1 个，组成 k 个一起。
时间复杂度分析：O(n)
C++ 代码
/*
最佳牛围栏
*/
#include <bits/stdc++.h>
#define LL long long int
using namespace std;
const int N = 100010;
double sum[N]; //前缀和
int dp[N];
int main(){
int n, k;
cin >> n >> k;
sum[0] = 0.0;
for (int i = 1; i <= n; i++) {
cin >> sum[i];
sum[i] += sum[i - 1];
}
dp[k] = 0; //第k个位置，只可能有一个最优。
for (int i = k + 1; i <= n; i++) {
double tx = double(sum[i] - sum[i - k] ) / k;
double ty = double(sum[i] - sum[dp[i - 1]]) / (i - dp[i - 1]);
if (tx > ty) dp[i] = i - k;
else dp[i] = dp[i - 1];
}
double res = 0;
for (int i = k; i <= n; i++) {
res = max(res, double(sum[i] - sum[dp[i]]) / double(i - dp[i]) );
}
int ans = res * 1000;
printf("%d\n", ans);
return 0;
}
这个方法是有问题的，就像贪心一样吧....
5 3
20 30 10 19 30
确实是个反例
谢谢，， 我理解了
话说这个反例ta的正解好像是30~第二个30
但是，我手动模拟了一下，不知道对不对：
首先，dp[3]=0
dp[4]=（经过计算）也是0
dp[5]=（又经过计算）还是0
这时，对于这个dp[5]，它的两种情况，一种是向前持续k(k=3)个
一种是直接到0
正解的情况直接就被忽略掉了
所以
这个思路确实类似贪心
但这道题所有子问题的最优解再加一位并不一定仍然最优
是会漏掉一些情况的
你好，这个解法是错的，我找了一个反例
5 3
2 3 1 2 3
这个解法其实是一种贪心，会漏掉一些情况，这里 31 2 3就漏了
条件 tx > ty 改成 tx >= ty 貌似就对了，短区间的优先级会更高
我修改了一下你的反例，似乎5 3 20 30 10 19 30是一个真正的反例
谢谢指出
有点难理解，不过这个思路绝了
我觉得这个方法有问题，i的最优位置不一定是i-1的最优位置，假如i-1的最优解很长，但i的最优解可能只取i-1前面更短的一部分，虽然这部分在i-1内不是平均值最大的，但a[i]的值足够大的话一样可以使得平均值更大，因为需要平均的部分变短了。
不好意思啊，我好久没有来这个网站了，你说的问题，我又想了一想。我也觉得有一些道理。然后，我举一个栗子，不知道，是不是你说的这样的。
首先 定义数列为 a,b,c,d,e,f, k = 3
从第k位开始。
abc
bcd
abcd
cde
bcde
abcde
def
cdef
bcdef
abcdef
上面的情况您应该可以理解。
您的说法，我理解的就是。 可以从 abcde 推出 bcdef. 而不是 由 abcde 推出abcdef.
因为 abcde -> bcdef 所以 avg(abcdef) < avg(bcdef)
等价于：
a+b+c+d+e+f b+c+d+e+f
---------------- < -----------------
6 5
也等价于
5a < b+c+d+e+f
然后我拆分一下为下面两个等式。 其中？ 号 表示不确定的 符号(<, >, =)
1： 4a ? b+c+d+e
2: a ? f
开始假设：
1. 两个 ？？ 分别为 = ， < : 也即是说 4a = b+c+d+e, 那么推出 abcdef 和 bcdef 都是合理的。
2. 两个？？ 分别分 =， >: 这不符合5a < b+c+d+e+f
3. 两个？？分别分 =, = : 这不符合5a < b+c+d+e+f
4. 两个? ? 分别分 <, < : 既然 4a < b+c+d+e , 那么 前一步选择的时候就应该是 bcde 而不是 abcde
5. 两个? ? 分别为 < =, 同 4
6. 两个? ? 分别为 <, > ， 同4
7. 两个? ？ 分别为 >, < , 这个时候，说明 f 比较大。那么选择 前一步就应该是 abcde, 而不是 bcde
8. 两个? ? 分别为 >, = 这不符合5a < b+c+d+e+f
9. 两个? ? 恩别为 >, > 这不符合5a < b+c+d+e+f
所以，我认为， abcdef 肯定是由 abcde 推出来的。而 bcdef 是由 bcde 推出来的。
我也不知道这样去想是不是对的，我在推理方面也比较弱。 如果有错误的地方，还望指出。
那样好像就不连续了吧
%%%%
这个解法相当好啊
大佬好棒啊!%%%%%%%%%%%%