首页 > 代码库 > HDU - 5124 lines
HDU - 5124 lines
Problem Description
John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.
Input
The first line contains a single integer T(1≤T≤100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line.
Output
For each case, output an integer means how many lines cover A.
Sample Input
251 2 2 22 43 45 100051 12 23 34 45 5
Sample Output
3 1
真是个好题，通过这个题我学会了离散化的一点知识，首先把所有的坐标映射到x轴上，然后将坐标压缩。怎么压缩呢？
可以用一个v数组，直接存贮位置就可以了，那么这样就完成了坐标的压缩。
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 #include <map> 5 #include <vector> 6 7 using namespace std; 8 9 #define MAXN 20000510 11 typedef pair<int,int> PII;12 13 int x[MAXN];14 PII p[MAXN];15 int v[MAXN];16 17 int main()18 {19 int t;20 scanf("%d",&t);21 while(t--){22 int n;23 scanf("%d",&n);24 int cnt = 0;25 for(int i = 0;i<n;i++){26 scanf("%d %d",&p[i].first,&p[i].second);27 x[cnt++] = p[i].first;28 x[cnt++] = p[i].second;29 }30 sort(x,x+cnt);31 cnt = unique(x,x+cnt)-x;32 for(int i = 0;i<cnt;i++){33 v[i] = 0;34 }35 int sum = 0;36 for(int i = 0;i<n;i++){37 int l = lower_bound(x,x+cnt,p[i].first)-x;38 int r = lower_bound(x,x+cnt,p[i].second)-x;39 v[l]++;40 v[r+1]--;41 }42 int s = 0;43 int mx = 0;44 for(int i = 0;i<cnt;i++){45 s+=v[i];46 mx = max(mx,s);47 }48 printf("%d\n",mx);49 }50 return 0;51 }
当然不一定非得把坐标映射到x轴上，vector <pair<int,int> > v; v[i].first 用来把坐标排序，起到了映射的作用。然后数组的下标就起到了压缩的作用。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 7 using namespace std; 8 9 vector <pair<int,int> > v;10 11 int main () {12 int T;13 cin >> T;14 while (T--) {15 v.clear();16 int N;17 scanf("%d",&N);18 for (int i = 0;i < N;i++) {19 int x;20 scanf("%d",&x);21 v.push_back(make_pair(x,1));22 scanf("%d",&x);23 v.push_back(make_pair(x + 1,-1));24 }25 sort(v.begin(), v.end());26 int ans = 0;27 int maxn = 0;28 for (int i = 0;i < v.size();i++) {29 ans += v[i].second;30 maxn = max(maxn,ans);31 }32 cout << maxn << endl;33 }34 }
HDU - 5124 lines
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。