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了。。

代碼：

#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;
}