题目描述

略

思路

最开始用暴力循环超时，然后改用前缀和，在ccf的oj上100分，在acwing上出现了segmental错误

C++ 代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
typedef long long ll;
int m;
typedef struct{
ll s;
int y;
int sum;
} ty;
ty t[N];


bool cmp(ty t1,ty t2){
    if(t1.s<=t2.s){
        if(t1.s<t2.s)
            return true;
        else if(t1.y<t2.y)
            return true;
    }
    else return false;
}

int main(){
    cin>>m;
    for(int i=0;i<m;i++){

        scanf("%d%d",&t[i].s,&t[i].y);



    }
    sort(t,t+m,cmp);//排序，注意cmp函数里面的一些细节
    t[0].sum=t[0].y;
    for(int i=1;i<m;i++)
        t[i].sum=t[i-1].sum+t[i].y;//计算前缀和
    ll res=t[0].s;
    int tomax=t[m-1].sum;
    for(int i=1;i<m;i++){

        ll tmp=t[i].s;
        if(tmp==t[i-1].s)continue;
        int cnt=0;
        cnt=i-t[i-1].sum+t[m-1].sum-t[i-1].sum;//有了排序+前缀和就可以轻轻松松求出正确预测数量，并且也可以保证是最大分数


        if(cnt>=tomax){
            tomax=cnt;
            res=tmp;

        }
    }
    cout<<res<<endl;
}