首页 > 代码库 > HDU5124：lines（线段树+离散化）或（离散化思想）

HDU5124：lines（线段树+离散化）或（离散化思想）

2024-08-06 11:02:32   217人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5124

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.
 
Output
For each case, output an integer means how many lines cover A.
 
Sample Input
2
5
1 2
2 2
2 4
3 4
5 1000
5
11
2 2
3 3
4 4
5 5
 
Sample Output
3
1
 题目解析：

题意：给定 n 个区间，问最多重复的子区间？

题解：（离散化思想）讲所有的数都排个序，将区间的左值定为 1 ，右值定为 -1 ，这样对所有的数搜一遍过去找最大的值即可；或者用线段树+离散化。

一：线段树

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#define N 100010using namespace std;struct  li{    int x,y;}line[N];struct node{    int l,r;    int lz;}q[8*N];int n,tt,X[2*N];int maxx;void build(int l,int r,int rt){    q[rt].l=l;    q[rt].r=r;    q[rt].lz=0;    if(l==r)        return ;    int mid=(l+r)>>1;    build(l,mid,rt<<1);    build(mid+1,r,rt<<1|1);    return ;}void pushdown(int rt){    if(q[rt].lz)    {        q[rt<<1].lz+=q[rt].lz;        q[rt<<1|1].lz+=q[rt].lz;        q[rt].lz=0;    }}void update(int lf,int rf,int l,int r,int rt){    if(lf<=l&&rf>=r)    {        q[rt].lz+=1;        return ;    }    pushdown(rt);    int mid=(l+r)>>1;    if(lf<=mid) update(lf,rf,l,mid,rt<<1);    if(rf>mid) update(lf,rf,mid+1,r,rt<<1|1);    return ;}void query(int l,int r,int rt){    if(l==r)    {       maxx=max(maxx,q[rt].lz);       return ;    }    pushdown(rt);    int mid=(l+r)>>1;    query(l,mid,rt<<1);    query(mid+1,r,rt<<1|1);    return ;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        tt=0;        maxx=-1;        scanf("%d",&n);        for(int i=0;i<n;i++)        {            scanf("%d%d",&line[i].x,&line[i].y);            X[tt++]=line[i].x;            X[tt++]=line[i].y;        }        sort(X,X+tt);        int sum=unique(X,X+tt)-X;        build(1,sum,1);        for(int i=0;i<n;i++)        {            int le=lower_bound(X,X+sum,line[i].x)-X+1;            int re=lower_bound(X,X+sum,line[i].y)-X+1;            if(le<=re)  update(le,re,1,sum,1);        }        query(1,sum,1);        printf("%d\n",maxx);    }    return 0;}

 二：离散化：思路：可以把一条线段分出两个端点离散化，左端点被标记为-1，右端点被标记为1，然后排序，如果遇到标记为-1，cnt++，否则cnt--;找出cnt的最大值。

#include <cstdio>#include <cstring>#include <algorithm>#define maxn 200010using namespace std;struct node{    int x,c;    bool operator<(const node &a)const    {        return (x<a.x)||(x==a.x&&c<a.c);    }}p[maxn];int t;int n;int main(){    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(int i=0; i<n; i++)        {            int s,e;            scanf("%d%d",&s,&e);            p[i*2].x=s;            p[i*2].c=-1;            p[i*2+1].x=e;            p[i*2+1].c=1;        }        sort(p,p+2*n);        int cnt=0; int ans=0;        for(int i=0; i<2*n; i++)        {            if(p[i].c==-1)            {                cnt++;            }            else                cnt--;            ans=max(ans,cnt);        }        printf("%d\n",ans);    }    return 0;}

可惜做BC时，这两种方法都没想出来，悲催！

 

#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <time.h>#include <ctype.h>#include <string>#include <queue>#include <set>#include <map>#include <stack>#include <vector>#include <algorithm>#include <iostream>#define PI acos( -1.0 )using namespace std;typedef long long ll;const int NO = 1e5 + 10;struct ND{    int x, y;}st[NO<<1];int n;bool cmp( const ND &a, const ND &b ){    if( a.x == b.x ) return a.y > b.y;    return a.x < b.x;}int main(){    int T;    scanf( "%d",&T );    while( T-- )    {        scanf( "%d", &n );        int cur = 0;        for( int i = 0; i < n; ++i )        {            scanf( "%d", &st[cur].x );            st[cur++].y = 1;            scanf( "%d", &st[cur].x );            st[cur++].y = -1;        }        sort( st, st+cur, cmp );        int ans = 0;        int Max = 0;        for( int i = 0; i < cur; ++i )        {            ans += st[i].y;            Max = max( ans, Max );        }        printf( "%d\n", Max );    }    return 0;}
View Code

 

HDU5124：lines（线段树+离散化）或（离散化思想）


联系
我们