Why so serious? --[NKU]schindlerlee

Feedback

# re: 2010年03月28日星期日.codeforces beta6 2010-03-28 07:54 MasterLuo

我覺得E二分是會(huì)有問題的？并不滿足單調(diào)性。
我有個(gè)想法就是用二條掃描線，外加一個(gè)最小堆來維護(hù)。  回復(fù)  更多評(píng)論   

# re: 2010年03月28日星期日.codeforces beta6 2010-03-28 10:08 schindlerlee

@MasterLuo
我覺得是單調(diào)的，肯定是前邊合法，后邊不合法了
還有就是我相信sgu那幫人做的動(dòng)不動(dòng)上百組的測試數(shù)據(jù)...
另外，我不太明白你說的掃描，我感覺那樣豈不是n^2了？


 1 for (i = 0;i < n;i++) {
 2     int L = i,R = n;
 3     while (L < R) {
 4         int mid = (L + R) / 2;
 5         int tmp = bigrmq(i,mid) - smlrmq(i,mid);
 6         if (tmp <= diff) {
 7             if (L == mid) { break;}
 8             L = mid;
 9         }else {
10             if (R == mid + 1) {break;}
11             R = mid + 1;
12         }
13     }
14     int tmp = L - i + 1;
15     if (tmp > ans) {
16         ans = tmp;
17         記錄結(jié)果
18     }else if (tmp == ans) {
19         記錄結(jié)果
20     }
21 }


  回復(fù)  更多評(píng)論   

# re: 2010年03月28日星期日.codeforces beta6 2010-03-28 10:48 MasterLuo

@schindlerlee
掃描是NlogN的，因?yàn)槲覀儚牡谝粋€(gè)開始每加入一個(gè)數(shù)后如果引起了不滿足題意條件，那么一定是最新加入的那個(gè)數(shù)引起的，現(xiàn)在還在堆中的最大數(shù)與最小數(shù)之間一定會(huì)有一個(gè)要退出，可以證明它與后面要加入的數(shù)也不能滿足條件。于是我們找到位置在前面的那個(gè)數(shù)，把它前面所有的數(shù)都刪除。再判斷，直到滿足條件為止。這樣每個(gè)數(shù)就只進(jìn)優(yōu)先隊(duì)列一次，也只出優(yōu)先隊(duì)列一次。 我寫了下代碼，驗(yàn)證了一下，過上去過了。
C++語言: 臨時(shí)自用代碼

int n, k, maxVal, minVal;   

int arr[100000], ans = 0, maxLen = 1, red[100000][2];

struct Node {

    int loc, val;

}node;

struct CMP_1 {

    bool operator()(const Node& min, const Node& max) {

         if((min.val > max.val) ||(min.val == max.val && min.loc > max.loc))

            return true;

        return false;

    }

};

struct CMP_2 {

    bool operator()(const Node& min, const Node& max) {

        if((min.val < max.val) || (min.val == max.val && min.loc > max.loc))

            return true;

        return false;

    }

};

int last = 0;

int main() {

    scanf("%d %d", &n, &k);

    for(int i = 0; i < n; ++i) {

        scanf("%d", &arr[i]);

    }

    priority_queue<Node, vector<Node>, CMP_1> pri;

    priority_queue<Node, vector<Node>, CMP_2> pri2;



    for(int i = 0; i < n; ++i) {

        node.val = arr[i];

        node.loc = i;

        pri.push(node);

        pri2.push(node);



        int minVal = pri.top().val;

        int maxVal = pri2.top().val;

        

        while(maxVal - minVal > k) {

            int lt = min(pri.top().loc, pri2.top().loc);

            while(!pri.empty() && pri.top().loc <= lt) {

                pri.pop();

            }

            while(!pri2.empty() && pri2.top().loc <= lt) {

                pri2.pop();

            }

            last = lt + 1;

            minVal = pri.top().val;

            maxVal = pri2.top().val;

        }

        int tmpLen = i - last + 1;

        if(tmpLen == maxLen) {

            red[ans][0] = last;

            red[ans][1] = i;

            ++ans;

        }

        if(tmpLen > maxLen) {

            red[0][0] = last;

            red[0][1] = i;

            ans = 1;

            maxLen = tmpLen;

        }

    }

    printf("%d %d\n", maxLen, ans);

    for(int i = 0; i < ans; ++i) {

        printf("%d %d\n", red[i][0] + 1, red[i][1] + 1);

    }

    return 0;

}