题目描述

ccf csp之期末预测。

算法

排序 + 前缀和

1.pair型数组a记录每个输入的两值。

2.对数组a进行排序。

3.s[0][i]，s[1][i]分别表示前i个数中0和1的个数。

4.t 表示每个数作为阈值时，预测正确的数量。

5.即时更新t, 并记录当前阈值即可。

注意 ： 遇到相同数时，应只算第一个！！！

时间复杂度

O(nlogn)

#include<iostream>
#include<algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 100010;

int s[2][N];
PII a[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i].first>>a[i].second;

    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < 2; j++)
        s[j][i] = s[j][i - 1] + (j == a[i].second);
    }

    int cnt = -1, res = 0;
    for(int i = 1; i <= n; i++)
    {
        int j = i;
        int t = s[0][i - 1] + s[1][n] - s[1][i - 1];
        while(j + 1 <= n && a[j + 1].first == a[i].first) j ++;
        if(t >= cnt) cnt = t, res = a[i].first;
        i = j;
    }
    cout<<res<<endl;
    return 0;
}

```