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

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

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

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

以下是按照题解做的，

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

（1）版本1 906 MS

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 #define x first
 9 #define y second
10 
11 const int N = 2e5 + 5;
12 pair<int, int> p[N];
13 
14 int main()
15 {
16     #ifndef ONLINE_JUDGE
17         freopen("in.txt", "r", stdin);
18     #endif // ONLINE_JUDGE
19     int t, n;
20     while (scanf("%d", &t) != EOF)
21     {
22         while (t--)
23         {
24             scanf("%d", &n);
25             int a, b, cnt = 0;
26             for (int i = 0; i < n; i++)
27             {
28                 scanf("%d%d", &a, &b);
29                 p[cnt++] = make_pair(a, 1);
30                 p[cnt++] = make_pair(b+1, -1);
31             }
32             sort(p, p+cnt);
33             int ans = 0, sum = 0;
34             for (int i = 0; i < cnt; i++)
35             {
36                 sum += p[i].y;
37                 if (sum > ans)
38                     ans = sum;
39                 if (sum < 0)
40                     sum = 0;
41             }
42             printf("%d
", ans);
43         }
44     }
45     return 0;
46 }

(2) 版本2 921 MS

将

for (int i = 0; i < cnt; i++)
{
      sum += p[i].y;
      if (sum > ans)
          ans = sum;
      if (sum < 0)
          sum = 0;
}

改成这样：

　　for (int i = 0; i < cnt; i++)
　　{
　　　　sum += p[i].y;
　　　　ans = max(ans, sum);
　　}

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

相关推荐