这道题题目啰嗦写的一塌糊涂根本搞不清楚什么意思。 其实简单得很,有一条线段 (实数轴) 长为 [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】