题目描述

根据题意描述 只需要分别计算当前数小于他且等于0的个数（les数组）加上大于等于他等于1的个数（more数组）再进行比较即可。因为给的数据是无序的，不太好处理，所以想到将每个数存进pair,先sort排序一下,此时发现对于当前数后面的数，我们的les和more数组完全可以复制一份给他，只需要减去比它小的数等于1的个数（more–）和加上比他小的数等于0的个数（les)即可，这大大降低时间复杂度。同时因为排过序了，可以开一个计算每个数个数的数组，循环时i变成i+num[i]即可，又大大降低时间复杂度。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef pair<int,int>PII;
PII a[N];
int ans;
unordered_map<int,int>les,more,num,res;
//用map存les more ans num数组，避免空间浪费。
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
        num[a[i].first]++;
    }
    sort(a+1,a+n+1);//排序后变为有序
    for(int i=1;i<=num[a[1].first];i++){
        if(a[i].second==1)more[a[i].first]++;
    }//只需要计算第一个数的more，后面的每一个数据直接copy即可（对于第一个数les一定为0）
    for(int i=num[a[1].first]+1;i<=n;i++){
        if(a[i].second==1)more[a[1].first]++;
    }
    res[a[1].first]+=more[a[1].first];//res=more+les
    ans=a[1].first;//记录答案
    int u=num[a[1].first];
    //从第二个数开始计算
    for(int i=u+1;i<=n;i+=num[a[i].first]){
        les[a[i].first]=les[a[i-1].first];//直接继承
        more[a[i].first]=more[a[i-1].first];
        int x=i-num[a[i-1].first];//只需要循环当前a[i]和a[i-1]即可
        for(int l=i-num[a[i-1].first];l<x+num[a[i-1].first]+num[a[i].first]-1;l++){
            if(a[l].first<a[i].first&&a[l].second==0)les[a[i].first]++;
            else if(a[l].first<a[i].first&&a[l].second==1)more[a[i].first]--;
        }
        res[a[i].first]+=les[a[i].first];
        res[a[i].first]+=more[a[i].first];
        if(res[a[i].first]>=res[ans])ans=a[i].first;//记录最大值
    }
  cout<<ans<<endl;
    return 0;
}