题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5124
题目意思：给出 n 条线段，每条线段用两个整数描述，对于第 i 条线段：xi，yi 表示该条线段的左端点和右端点。设 A 表示最多线段覆盖的点（当然这个 A 可以有多个啦，但这个无关紧要）。现在需要求的是 A 被多少条线段覆盖。
我是不会做啦.......一开始还看不懂题目= =
以下是按照题解做的，
题解中的最大区间和，实际上就是求最大连续子序列的和。
（1）版本1 906 MS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; #define x first
#define y second const int N = 2e5 + ;
pair<int, int> p[N]; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int t, n;
while (scanf("%d", &t) != EOF)
{
while (t--)
{
scanf("%d", &n);
int a, b, cnt = ;
for (int i = ; i < n; i++)
{
scanf("%d%d", &a, &b);
p[cnt++] = make_pair(a, );
p[cnt++] = make_pair(b+, -);
}
sort(p, p+cnt);
int ans = , sum = ;
for (int i = ; i < cnt; i++)
{
sum += p[i].y;
if (sum > ans)
ans = sum;
if (sum < )
sum = ;
}
printf("%d\n", ans);
}
}
return ;
}
(2) 版本2 921 MS
将
for (int i =; i < cnt; i++)
{
sum += p[i].y;
if (sum > ans)
ans = sum;
if (sum <)
sum =;
} 改成这样：
for (int i = 0; i < cnt; i++)
{
sum += p[i].y;
ans = max(ans, sum);
}