[思路题] hdu 5124 lines

题意：

给n个区间 [x,y]，问被最多覆盖的点，被覆盖了多少次。

思路：

一个很巧妙的方法。好像原来有接触过。

就是如果给你[1,3]就used[1]++，used[4]--。

然后从左到又过一遍出现的点 依次累加每次加的时候取最大值。

然后这题需要用到map离散化。

代码：

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
#include"stack"
#include"vector"
#define ll __int64
#define inf -999999999999999999LL
using namespace std;
int a[123456],b[123456];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int cnt=1;
        int n;
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        map<int,int>mp;
        while(n--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            y++;
            if(!mp[x])
            {
                b[cnt]=x;
                mp[x]=cnt++;
            }
            if(!mp[y])
            {
                b[cnt]=y;
                mp[y]=cnt++;
            }
            a[mp[x]]++;
            a[mp[y]]--;
        }
        sort(b+1,b+1+cnt);
        int sum=0,ans=0;
        for(int i=1;i<cnt;i++)
        {
            sum+=a[mp[b[i]]];
            ans=max(sum,ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}

[思路题] hdu 5124 lines

原文：http://blog.csdn.net/wdcjdtc/article/details/45341139