HDU 5124 lines - dblank

HDU 5124 lines

lines

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1439    Accepted Submission(s): 594

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(1T100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1N105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1XiYi109),describing a line.

 

Output
For each case, output an integer means how many lines cover A.
有两种方法:
第一种是直接把端点排序,起点的值为1,终点的值为-1,然后过一遍取最大值。
#include<iostream>  
#include<algorithm>  
#include<cstring>  
#include<cstdio>  
#include<queue>  
#include<vector>  
#include<map>  
#include<cmath>  
#include<fstream>  
#include<stack>  
using namespace std;  
typedef long long ll;  
struct node  
{  
    int x, v;  
}s[200020];  
int cmp(node a, node b)  
{  
    if(a.x == b.x)  
        return a.v>b.v;  
    return a.x <b.x;  
}  
int main()  
{  
   int t, n;  
   cin>>t;  
   while(t--)  
   {  
       scanf("%d", &n);  
       for(int i = 0; i<n; i++)  
       {  
           scanf("%d", &s[i<<1].x);  
           s[i<<1].v = 1;  
           scanf("%d", &s[i<<1|1].x);  
           s[i<<1|1].v = -1;  
       }  
       sort(s, s+2*n, cmp);  
       int cnt = 0, ans = 0;  
       for(int i = 0; i<2*n; i++)  
       {  
           cnt += s[i].v;  
           ans = max(cnt , ans);  
       }  
       cout<<ans<<endl;  
   }  
}

第二种:先离散化,然后线段树区间更新,取最大值。

#include<iostream>  
#include<algorithm>  
#include<cstring>  
#include<cstdio>  
#include<queue>  
#include<vector>  
#include<map>  
#include<cmath>  
#include<fstream>  
using namespace std;  
struct node  
{  
    int l,r, maxx, mark;  
} s[200200<<2];  
int x[200020], k, a[100010], b[100010];  
void pushup(int cnt)  
{  
    s[cnt].maxx = max(s[cnt<<1].maxx , s[cnt<<1|1].maxx);  
}  
void pushdown(int cnt)  
{  
    if(s[cnt].mark)  
    {  
        //int l = len - (len/2);  
        s[cnt<<1].mark += s[cnt].mark ;  
        s[cnt<<1|1].mark += s[cnt].mark;  
        s[cnt<<1].maxx += s[cnt].mark;  
        s[cnt<<1|1].maxx += s[cnt].mark;  
        s[cnt].mark = 0;  
    }  
}  
void build_tree(int l, int r, int cnt)  
{  
    s[cnt].l = l;  
    s[cnt].r = r;  
    s[cnt].maxx = 0;  
    s[cnt].mark = 0;  
    if(l == r)  
        return ;  
        int m= (l+r)>>1;  
    build_tree(l, m, cnt<<1);  
    build_tree(m+1, r, cnt<<1|1);  
}  
void update(int l, int r, int cnt)  
{  
    if(s[cnt].l >= l && s[cnt].r <= r)  
    {  
        s[cnt].mark += 1;  
        s[cnt].maxx += 1;  
        return ;  
    }  
    pushdown(cnt);  
    int m = (s[cnt].l + s[cnt].r)>>1;  
    if(l <= m)  
        update(l, r, cnt<<1);  
    if(r > m)  
        update(l, r, cnt<<1|1);  
    pushup(cnt);  
}  
int main()  
{  
    int t, n, u, v;  
    cin>>t;  
    while(t--)  
    {  
        scanf("%d", &n);  
        k = 0;  
        for(int i = 1; i<=n; i++)  
        {  
            scanf("%d%d", &a[i], &b[i]);  
            x[k++] = a[i];  
            x[k++] = b[i];  
        }  
        sort(x,x+2*n);  
        //for(int i = 0; i<2*n; i++)  
      //      printf("%d ", x[i]);  
      //  printf("\n");  
        build_tree(1, 2*n, 1);  
        for(int i = 1; i<=n; i++)  
        {  
            int l = lower_bound(x, x+2*n, a[i]) - x + 1;  
            int r = lower_bound(x, x+2*n, b[i]) - x + 1;  
          //  printf("%d %d %d %d\n", l, r, a[i], b[i]);  
            update(l, r, 1);  
        }  
        printf("%d\n", s[1].maxx);  
    }  
    return 0;  
}

 

发表新评论