zoj 3518 – Unsafe Factor

又是一道区间题,这题其实可以用一种非常优美的方式理解,开始一不小心被绕进去了。

有两条胶带,上面分布了一些不相交的已损坏区间,求最长的只有一边已损坏区间的长度。

其实题目说保证两段胶带的已损坏区间不重复,这个条件就可以理解成把所有区间合并在一起,转化成异或为 1 的区间段,求其中最长的。

那么其实就根本不用管是 n1 还是 n2,我们一起处理,然后对于输入的 (l, r) 整数格区间,我们转换成 (l, r+1) 的自然区间,然后做一个 bool map,对每个输入的区间,map[l] 个 map[r+1] 都进行一个翻转。

最后,遍历 map,就可以得到所有的区间,结论就出来了。

// 3493789 2013-12-22 00:35:48 Accepted 3518 C++ 170 11464 呆滞的慢板

include

include

include

include

using namespace std;

int main() {

int L, n1, n2, l, r;

while(scanf("%d%d%d", &L, &n1, &n2) != EOF) {
    map<int, int> mp;
    for(int i = 0; i < n1+n2; ++i) {
        scanf("%d%d", &l, &r);
        mp[l] ^= 1;
        mp[r+1] ^= 1;
    }
    int mx = 0, x = 0;
    for(map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
        if(it->second) {
            if(x ^= 1) l = it->first;
            else mx = max(mx, it->first - l);
        }
    }
    printf("%d\n", mx);
}

}


【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3518.html【zoj 3518 – Unsafe Factor】

发表评论

电子邮件地址不会被公开。 必填项已用*标注