2015年4月10日 星期五

[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) ;
}
 

沒有留言:

張貼留言