hdu 5124 BestCoder #20 1002 lines 解题报告

这道题和以前做过的一道很像,然后哗啦哗啦就敲了提交了,然后pretest pass了 ,交了以后发现有问题,我的方法只是对一维数组进行标记然后扫描一遍,但是对于1e9的数据不仅爆数组又会T。想了一会儿怎么改进,最后还是卡这了。

赛后想了想,做一个简单的映射就行了,在原来的数组上相当于再加一层数组,对当前数组的index也就是上层数组的value进行标记扫描,就好过了。。。

将线段的x和y都放在一个数组v里,然后对2*n大小的v数组排序,然后对于每一个x,二分查找v数组的lower_bound,然后标记++,对于每一个y,二分查找v数组的lower_bound,然后标记–,最后扫描一遍OK了。。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int a[maxn],b[maxn];
int f[maxn * 2];
int v[maxn * 2];
int main()
{
freopen("in.txt","r",stdin);
int T;
cin>>T;
while(T--)
{
int n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(f,0,sizeof(f));
memset(v,0,sizeof(v));
scanf("%d",&n);
for(int i = 0 ; i <n ; i++)
{
scanf("%d%d",&a[i],&b[i]);
f[i] = a[i];
f[i+n] = b[i];
}
sort(f,f+n*2);
for(int i = 0; i < n ; i++)
{
int aa = lower_bound(f, f+2*n,a[i])-f;
int bb = lower_bound(f, f+2*n, b[i])-f;
v[aa]++;
v[bb+1]--;
}
int tmp = 0,ans= 0;
for(int i = 0 ; i < n*2;i++)
{
tmp += v[i];
ans = max(ans,tmp);
}
printf("%d\n",ans);
}
return 0;
}