斜率優化

今天多虧了J睿的福，我很清楚的了解了斜率優化的基礎，

並自己透過概念，想出一套錯誤的演算法，再經J睿的修正，得出這個算法的正確形象

感謝最愛J!NN的J1SS睿～～～>//////<

他並不是很難，看到下面這個基本的斜率優化code就知道了，精神不過五行。

//By momo
#include<cstdio>
int s[100010],dq[100010],f,e,r,L,R,x,y,t,n,k,i;
bool crs( int a,int b,int c ){
    return 1ll*(s[b]-s[a])*(c-b)>1ll*(s[c]-s[b])*(b-a);
}
int main(){
    scanf("%d",&t);
    while( t-- ){
        scanf("%d%d\n",&n,&k);
        for( s[0]=f=e=y=0,i=x=1; i<=n;i++) r=getchar(),s[i]=s[i-1]+r-'0';
        for( i=k; i<=n; i++ ){
            while( f<e-1 && crs(dq[e-2],dq[e-1],i-k) ) e--; dq[e++]=i-k;
            while( f<e-1 && !crs(dq[f],dq[f+1],i) ) f++;
            if( 1ll*y*(i-dq[f])<1ll*x*(s[i]-s[dq[f]]) 
             || 1ll*y*(i-dq[f])==1ll*x*(s[i]-s[dq[f]]) && i-dq[f]<R-L )
                x=i-dq[f], y=s[i]-s[dq[f]], L=dq[f], R=i;
        }
        printf("%d %d\n",L+1,R);
    }
}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝今天就快速進入正題，code已附上

他基本上用來解的題目是這樣子的－Q:給一個序列（有N個值），問長度大於等於K的最大平均和?

預先操作為將序列轉成sum[i]序列（就是由a0+...+ai），題目也轉成在座標平面上（x為i值，y為sum[i]值），選出兩點使(sum[i]-sum[j])/(i-j)的值最大（其中i-j+1>=K），也就是斜率最大（故稱為斜率優化）

naive作法：枚舉i並枚舉他的j，O(n^2)，爛作法-3-

這時，你重新的看一下你想要做的事情：

你其實想要做的是對於所有的i，要從K限制以下的點中，找出一點，使i節點與那一個點的斜率最大。

而從幾何上看來，即為一個圍起來的凸多邊形，而在 此多邊形 外的點，要與其中的所有點有最大斜率or最小斜率時，其必出現在端點上（線性規劃的精隨）。

（pf: 一個不是端點的點，代表在一個距離為e的圓（或半圓）內必存在另一個也在此多邊形中的點，若此點有最大斜率，則在此點指向i的向量順時針轉180度的範圍內移動e，皆可使斜率變大（反之則斜率變小），故唯有某一端點才會有最大斜率）

這時你就得到一個較快速的方法，求出前面的凸包，一個一個枚舉，而你又可以知道上半部的凸包並不是最大的（反而是最小的），原因如同上面的證明，所以你只需要記錄下凸包即可，但複雜度仍為O(n^2)。（下凸包定義：斜率遞增，且不會有點在此函數下方）

再多想一下你想要找的是什麼：

你發現了其實你要找的是一個切點－定義為與i形成的直線『斜率最大』的點－，經過一些直覺的猜想與證明，你知道這個切點與i形成的直線斜率要介於這個切點與兩個邊所形成的直線斜率之間，把它做切塊后，你可以很清楚的看到這樣的點只有一個，除非是在邊上（如圖所示），而且每個點與i形成的斜率會呈現遞增再遞減的趨勢。

{性質：斜率會是遞增再遞減，而切點則是使與i形成的斜率介於兩個邊所形成的直線斜率之間，且唯一}

pf:先證遞減，同理可證遞增

pf:再證當斜率介於這個切點與兩個邊所形成的直線斜率之間，則斜率比兩邊都還要大

這時你就可以用一個二分搜的方法求出切點，演算法複雜度：O(nlgn)，但這並不是最好的，因為再多看一下我放的第二張圖，你會發現當你做到某一切點時，前面的點都可以刪掉了，因為若之後的點會把前方的點當做切點時，他的斜率必介於兩個邊的斜率之間，而且邊的斜率遞增，所以這個斜率一定會小於現在做到的斜率，故你也不需要去看前面的點了。加上這個單調性優化，複雜度變成了O(n)。