[USACO 2014 Gold] Sabotage

作法：

原題要求的東西簡單來說就是：求出兩段不相交的前綴和後綴，使得他們合起來的平均值最小。而兩段分開的很不好算，所以如果把整個數列延長一倍，變成長為 2*n 的數列，使得 a_( i+n ) = a_i，這樣等於是要求出一段包含 a_n 和 a_( n+1 ) 的數列，使得平均值最短，而且長度不能超過 n-1 （題目說至少要砍掉一個數，也就是剩下的數至少要有 n-2 個）。不難看出這個問題和以下問題非常類似：給定一個數列，求出他的平均值最大的連續子數列，並且長度必須>=某個定值。這個問題的作法是考慮前綴和，加上DP斜率優化，這裡的問題也可以用很類似的方法做。

具體來說，首先當然是先求出前綴和，設前綴和陣列為 S[ i ] ，那麼現在就變成要求出兩個數 i , j 使得 i <= n-1 < n <= j ， j - i <= n-1 ，並且點 ( i , S[ i ] ) 到點 ( j , S[ j ] ) 的斜率越小越好。考慮按照右端點由大到小做，每次加入合法的新的左端點，並且在左端點的部份維護一個凹向下的點集，還有當前的最佳點，每次詢問時如果最佳點的右邊更好就讓他往右跑，直到不會更好的時候拿他去更新答案。

code :

#include<bits/stdc++.h>
#define DB double
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
int a[2*maxn] ;
int s[2*maxn] ;
main()
{
    if(fopen("sabotage.in","r"))
    {
        freopen("sabotage.in","r",stdin) ;
        freopen("sabotage.out","w",stdout) ;
    }
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        a[i]=a[i-1]+x ;
    }
    for(int i=n+1;i<2*n;i++) a[i]=a[n]+a[i-n] ;
 
    DB ans=1e6 ;
    int sz=0 ;
    for(int i=2*n-2,j=0;i>=n+1;i--)
    {
        while(sz>=2 && (LL)(s[sz-2]-s[sz-1])*(a[s[sz-1]]-a[i-n+1])
              <= (LL)(a[s[sz-2]]-a[s[sz-1]])*(s[sz-1]-(i-n+1)))
            sz-- ;
        s[sz++]=i-n+1 ;
        j=min(j+1,sz-1) ;
        while(j && (LL)(i-s[j-1])*(a[i]-a[s[j]])
                >= (LL)(a[i]-a[s[j-1]])*(i-s[j]))
            j-- , sz-- ;
        ans=min(ans, ((DB)a[i]-a[s[j]])/((DB)i-s[j]) ) ;
    }
    printf("%.3f\n",ans) ;
}