POJ 2018 Best Cow Fences

Description

N, K: 有n个农场，每个农场有不同数目的牧场，圈起不少于K个农场，用其牧场数 / 农场数 * 1000求最大值

题目链接

二分

第一次

因为涉及”连续项的和“，所以用前缀和维护

bool judge(mid) 遍历所有方案，若有均值 >= mid 则return 1

但我只考虑了圈起k个农场的情况，忽略了 > k方案，WA

#include <cstdio>
#include <iostream>
using namespace std;

int n, k;
double a[100010];
double sum[100010];

bool judge(double ans)
{
    for(int i = k; i <= n; ++i)
        if(sum[i] - sum[i - k] > ans * k)
            return 1;
    return 0;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lf", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    double mid, l = 0, r = 1e7;
    while(r - l > 1e-6)
    {
        mid = (l + r) / 2;
        if(judge(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.f\n", 1000 * l);
    return 0;
}

第二次

外加一层循环，果然还是TLE了

#include <cstdio>
#include <iostream>
using namespace std;

int n, k;
double a[100010];
double sum[100010];

bool judge(double ans)
{
    for(int t = k; t <= n; ++t)
        for(int i = t; i <= n; ++i)
            if(sum[i] - sum[i - t] > ans * double(t))
                return 1;
    return 0;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lf", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    double mid, l = 0, r = 1e6;
    while(r - l > 1e-6)
    {
        mid = (l + r) / 2;
        if(judge(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%d\n", int(1000 * r));
    return 0;
}

第三次

考虑能不能两层循环优化为一层：我两层循环是在遍历所有方案，依次检验是否有符合条件的情况，但实际我只需要拿“最有可能符合条件”的那一个方案去检验即可，就像：一个集合内的最大值都<n，则没有大于n的值。！！！

找“符合方案的最大均值”不好搞，没有规律、没有方法去找，然后这里有一个转化思想：

比较 ( 均值 > mid ? ) 等同于 (均值 - mid > 0 ?) 等同于 ((每个值 - mid)总和 > 0 ?)

那就只用一层循环，i 从1到 n - k，用一个量mmin存这里面最小的sum[i]，用一个量mmax存sum[i + k]里面最大的。这个想法还不对，可能前一个对应sum[n - k]，后一个对应sum[1 + k]，那两者距离相差可能小于k。

所以要控制间距。每次循环更新“最可能符合条件的方案”：mmin更新最小sum[i]，但另一个量ans = max(ans, sum[i + k] - mmin)，必能找到最优方案ans，且保证对应两者距离>=k，因为mmin <= 当前循环的i，他距离i + k的距离也因此而 >= k(妙不可言)

#include <cstdio>
#include <iostream>
using namespace std;

int n, k;
double a[100010];
double sum[100010];

bool check(double mid)
{
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + a[i] - mid;
    double mmin = 1e9;
    double ans = -1e9;
    for(int i = k; i <= n; ++i)
    {
        mmin = min(mmin, sum[i - k]);
        ans = max(ans, sum[i] - mmin);
    }
    return ans > 0;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%lf", &a[i]);
    double mid, l = 0, r = 1e6;
    while(r - l > 1e-6)
    {
        mid = (l + r) / 2;
        if(check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%d\n", int(1000 * r));
    return 0;
}

还有件事，我之前的二分最后一直是输出左界（按理说左界==右界），但在这里输出左界不对，右界对了……