这个题让自己弄明白了什么是离散化。其实可以用树状数组和线段树储存,不过用一个数组来模拟树状数组的思想也是可以的,数据量不是很大。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn];
int f[maxn<<1];
int v[maxn<<1];
int main(){
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(f,0,sizeof(f));
		memset(v,0,sizeof(v));
        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<<1));
        int len = unique(f,f+2*n)-f;
        for(int i=0;i<n;i++){
	    	int aa=lower_bound(f,f+len,a[i])-f;
	    	int bb=lower_bound(f,f+len,b[i])-f;
	    	v[aa]++;
	    	v[bb+1]--;
	    }
        int temp = 0, ans = 0;
        for(int i=0;i<len;i++){
            temp+=v[i];
            ans = max(ans,temp);
        }
        printf("%d\n",ans);
    }
    system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注