首页 > ACM题库 > HDU-杭电 > HDU 3581-Judge Segments-大数据-[解题报告]HOJ
2014
11-27

HDU 3581-Judge Segments-大数据-[解题报告]HOJ

Judge Segments

问题描述 :

There are many segments and many points. For each pair of points, we get a segment between them. Calculate how many given segments contains the segment. If two points are in the same location, the result is how many given segments contains the point.
Note: Segment [1,10] contains the segment made by point 1 and point 10.

输入:

Multi-testcase. An integer t indicate the number of test cases. t is less than 20.
For each test case, n and m ( 0 <= n <= 100000,0 <= m <= 500 ) indicate the number of segments and the number of points.
Following n lines, each line input two numbers a, b ( 0 <= a < b <= 100000 ) indicate the given segments.
Following m numbers, c ( 0 <= c <= 10^6 ) indicate all the points. All the points are given in non-decreasing order.

输出:

Multi-testcase. An integer t indicate the number of test cases. t is less than 20.
For each test case, n and m ( 0 <= n <= 100000,0 <= m <= 500 ) indicate the number of segments and the number of points.
Following n lines, each line input two numbers a, b ( 0 <= a < b <= 100000 ) indicate the given segments.
Following m numbers, c ( 0 <= c <= 10^6 ) indicate all the points. All the points are given in non-decreasing order.

样例输入:

2
2 4
2 5
1 4
1 2 4 5
2 4
1 4
6 9
1 4 6 9

样例输出:

Case 1:
1 1 1 0
1 2 2 1
1 2 2 1
0 1 1 1

Case 2:
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1


题意http://acm.hdu.edu.cn/showproblem.php?pid=3581
//扫描线求线段覆盖
//For each
pair of points, we get a segment between them. Calculate how many
given
//segments
contains the segment. If two points are in the same location, the
result
//is how
many given segments contains the point.
官方解题报告:
先把线段按结尾排序
枚举起点点,O(n)找出所有起点在这个点之前的线段,然后枚举结尾点,一边枚举一边扫过去所有的线段,如果结
尾已经在这个线段的结尾之后了就cnt–。总复杂度O(mn+m^2+nlogn),其实按理论算的话有点紧,不过大数据其实
只有2组。
//学会总结规律,避免重复计算以避免TLE,坚决拒绝CE,RE,PE等弱智罚时错误!!!
############################################Source
Code:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using
namespace std;
struct
segment
{
int s, e;
bool operator <(const segment
&t)const
{
return e>t.e;
}
}seg[100005];
int
p[505], n, m;
int
num[505][505];
bool
cmp(segment a, segment b)
{
if(a.s==b.s)return a.e<b.e;
return a.s<b.s;
}
int
main()
{
//freopen(“J.in”, “r”, stdin);
//freopen(“out.txt”, “w”, stdout);
int t, ca, i, j, k;
scanf(“%d”, &ca);
for(t=1; t<=ca; t++)
{
scanf(“%d%d”, &n, &m);
for(i=0; i<n; i++)
scanf(“%d%d”, &seg[i].s,
&seg[i].e);
sort(seg, seg+n, cmp);
for(i=0; i<m; i++)
scanf(“%d”, &p[i]);
memset(num, 0, sizeof(num));
segment ts;
      k=0;
for(i=0; i<m; i++)
{
priority_queue<segment>
q;//优先队列里按结尾排
for(; k<n; k++)//压入没覆盖i-1点但是覆盖i点的线段
{
if(seg[k].e<p[i])continue;
if(seg[k].s>p[i])break;
   q.push(seg[k]);
}
for(j=i; j<m; j++)
{
if(i!=0)num[i][j]=num[i-1][j];//注意应用已知的条件
while(!q.empty())
{
ts=q.top();
if(ts.e>=p[j])break;
q.pop();
}
num[i][j]+=q.size();
num[j][i]=num[i][j];
}
}
printf(“Case %d:\n”, t);
for(i=0; i<m; i++)
{
for(j=0; j<m-1; j++)
printf(“%d “, num[i][j]);
printf(“%d\n”, num[i][j]);
}
printf(“\n”);
}
return 0;
}
参考:http://blog.sina.com.cn/s/blog_6a46cc3f0100t3xi.html


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。