Why so serious? --[NKU]schindlerlee

Feedback

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

我觉得E二分是会有问题的？并不满足单调性。
我有个想法就是用二条扫描线，外加一个最小堆来维护。  回复  更多评论   

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

@MasterLuo
我觉得是单调的，肯定是前边合法，后边不合法了
还有就是我相信sgu那帮人做的动不动上百组的测试数据...
另外，我不太明白你说的扫描，我感觉那样岂不是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         记录结果
18     }else if (tmp == ans) {
19         记录结果
20     }
21 }


  回复  更多评论   

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

@schindlerlee
扫描是NlogN的，因为我们从第一个开始每加入一个数后如果引起了不满足题意条件，那么一定是最新加入的那个数引起的，现在还在堆中的最大数与最小数之间一定会有一个要退出，可以证明它与后面要加入的数也不能满足条件。于是我们找到位置在前面的那个数，把它前面所有的数都删除。再判断，直到满足条件为止。这样每个数就只进优先队列一次，也只出优先队列一次。 我写了下代码，验证了一下，过上去过了。
C++语言: 临时自用代码

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;

}