BestCoder20 1002.lines (hdu 5124) 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5124

题目意思:给出 n 条线段,每条线段用两个整数描述,对于第 i 条线段:xi,yi 表示该条线段的左端点和右端点。设 A 表示最多线段覆盖的点(当然这个 A 可以有多个啦,但这个无关紧要)。现在需要求的是 A 被多少条线段覆盖。

我是不会做啦.......一开始还看不懂题目= =

以下是按照题解做的,

BestCoder20 1002.lines (hdu 5124) 解题报告

  题解中的最大区间和,实际上就是求最大连续子序列的和。

(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);
  }

上一篇:BestCoder6 1002 Goffi and Squary Partition(hdu 4982) 解题报告


下一篇:BestCoder16 1002.Revenge of LIS II(hdu 5087) 解题报告