「USACO14MAR」破坏Sabotage

给出一段区间 \(w[1...n]\)，要求去掉其中一段子区间使得区间剩下部分平均值最大，且不能去掉头和尾，去掉的区间长度 \(len\ge1\) 。其中 \(3\le n\le 10^5\) 。

Luogu

分析

0/1 分数规划问题。

因为一段区间的平均值为 \(\frac{\sum_{d=i}^jw[d]}{j-i+1}\) ，所以我们可以用前缀和的思想，设 s[i] 为前 \(i\) 项的和。

假设要去掉区间为 \(i\) 至 \(j(i<j)\) ，剩下的区间的平均值为 \(t\)，则有

\[s[n]-s[j]+s[i-1]=t(n-j+i-1)\]

移项得

\[s[n]-t*n-(s[j]-t*j-s[i-1]+t*(i-1))=0\]

于是我们设 \(d[i]=s[i]-t*i\)，

\[d[n]-(d[j]-d[i-1])=0\]

易知，当 \(d[n]>d[j]-d[i-1]\) 时，一定有比 \(t\) 更好的答案，当 \(d[n]=d[j]-d[i-1]\) 时， \(t\) 就是最优解，所以我们可以用二分来逐渐逼近最优解，找到答案。

于是我们只需找到 \(max(d[j]-d[i-1])\) ，判断其是否小于 \(d[n]\) 即可，但由于直接找 \(max(d[j])\) 和 \(min(d[i-1])\) 不好使 \(i<j\) ，所以我们用 mx[] 和 mn[] 来记录最大与最小值，显而易见，若 \(max(d[j]-d[i-1])\le d[n]\) ，则每一对 \(d[j]-d[i-1]\) 一定小于等于 \(d[n]\) ，故我们每次判断 \(mx[i]-mn[i-1]\) 是否小于等于 \(d[n]\) 就好了。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eps 1e-7
#define N 100003
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;
typedef double db;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

int n;
int w[N], s[N];
db d[N], mx[N], mn[N];

bool check(db t) {
    for (int i = 1; i <= n; ++i) d[i] = s[i] - t * i;
    mn[1] = d[1], mx[n-1] = d[n-1];
    for (int i = 2; i < n - 1; ++i) mn[i] = min(mn[i-1], d[i]);
    for (int i = n - 2; i; --i) mx[i] = max(mx[i+1], d[i]);
    for (int i = 2; i < n; ++i)
        if (mx[i] - mn[i-1] > d[n]) return 0;
    return 1;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(w[i]), s[i] = s[i-1] + w[i];
    db l = 0, r = (s[n] - s[n-1] + s[1]) / 2.0;
    while (r - l > eps) {
        db mid = (l + r) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.3lf", l);
    return 0;
}

「USACO14MAR」破坏Sabotage

原文：https://www.cnblogs.com/hlw1/p/12260544.html