轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年5月24日 星期六

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已經被包含在這個算法裡了,所以不用特別去處理,一開始我一直搞不清楚。

#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;
}