zoj 3573 – Under Attack

这道题题目啰嗦写的一塌糊涂根本搞不清楚什么意思。 其实简单得很,有一条线段 (实数轴) 长为 [0, L],初始值为 0,每次往区间 [start, end] 上面加一个值 d,求最大值出现的最左位置和最右位置。

于是很简单,因为区间不长,记录变化点即可,设定 v[0..L+1] 每录入一个 (l, r, d),令 v[l] += d, v[r+1] -= d。 然后 i 从 0 到 L+1 遍历,每次加上 v[i],就可以得到该点的值。这样完全就是一个线性复杂度的操作。

// 3493756 2013-12-21 23:12:26 Accepted 3573 C++ 3020 272 呆滞的慢板

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main() {

    int L, l, r, x, mx, i, v[15002];

    while(cin >> L) {
        memset(v, 0, sizeof(v));
        while(cin >> l >> r >> x) {
            if(l < 0) break;
            v[l] += x;
            v[r+1] -= x;
        }
        mx = 0;
        x = 0;
        for(i = 0; i <= L+1; ++i) {
            x += v[i];
            if(x > mx) {
                mx = x;
                l = r = i;
            }
            else if(x == mx) {
                r = i;
            }
        }
        cout << l << ' ' << r << endl;
    }

}

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

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3573.html【zoj 3573 – Under Attack】

发表评论

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