Code 備忘錄►Divide & Conquer

TOJ::161 / 高棕櫚溫室

http://2014.sprout.csie.org/oj/pro/161/
題目是有幾個區間和大於等於K，最難的地方是區間和可能有負數，不能用爬行法解。

這題的解法之一是用分治法。
先將0到n-1的陣列轉換成0到n的前綴和(第0項是0，第一項是原本的第0項，第n項是原本的第0到第n-1的和)。
再來對前綴和陣列做merge sort，但是要改一點東西。
對於左邊和右邊的數字合併時，如果右邊某一個數減左邊某一個數大於等於K，就代表有一個區間和大於等於K。因為合併時，左邊和右邊還沒混在一起，所以這是一個合法的區間和。
因此我們每舉左邊和右邊的前綴和，就能得到有幾個區間大於等於K，但是這樣複雜度為退化到O(n^2)。
不過，因為左右都排序好了，就會有單調性，先枚舉右邊，看看左邊到第幾個為止連續和大於K，之後右邊往右一格，可以發現原本大於K的左邊一定還是大於K，所以左邊的範圍只會往右增加。因此，用雙指針I、J，分別從左界和中間開始，只要SUM[J]-SUM[I]>=K，I++，之後更新個數，J++，做完順便merge sort。
PS.注意區間長度是1的case已經被包含在這個算法裡了，所以不用特別去處理，一開始我一直搞不清楚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 100001
#define LL long long
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int D[N],ST[N];
LL DC(int l,int r,int k){
    if(l==r)return 0;
    int i=l,st=l;
    LL sum=0;
    int p=l,mid=(l+r)/2;
    sum+=DC(l,mid,k)+DC(mid+1,r,k);
    for(int j=mid+1;j<=r;j++){
        while(i<=mid&&D[i]<=D[j])ST[st++]=D[i++];
        while(p<=mid&&D[j]-D[p]>=k)p++;
        sum+=(LL)(p-l);
        ST[st++]=D[j];
    }
    while(i<=mid)ST[st++]=D[i++];
    for(i=l;i<=r;i++)D[i]=ST[i];
    //cout<<"DD "<<l<<' '<<r<<' '<<sum<<endl;
    return sum;
}
int main(int argc,char *argv[])
{
    ios_base::sync_with_stdio(false);
    int n,m;
    cin>>n;
    while(cin>>n>>m){
        Fl(i,1,n+1){
            cin>>D[i];
            D[i]+=D[i-1];
        }
        cout<<DC(0,n,m)<<endl;
    }
    return 0;
}