期末预测之最佳阈值

1. pair排序：默认对first按照升序排序，first相同时，按照second升序排序。

2. 前缀和

3. 需要考虑特殊情况：输入包含多个相同的安全指数 y 的处理

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 100005;
int y[N][2] = {0}; // 前缀和
pair<int, int> a[N]; // 输入

int main(){
    // 输入
    int n; cin >> n;
    for(int i=0; i<n; i++) cin >> a[i].first >> a[i].second;
    sort(a, a+n);

    // 解题（统计前缀和）
    for(int i=1; i<=n; i++){
        y[i][0] = y[i-1][0] + !a[i-1].second;
        y[i][1] = y[i-1][1] + a[i-1].second;
    }

    // (找答案)
    int ans; int p=-1; int t;
    for(int i=0; i<n; i++){
        if(i>0 && a[i].first == a[i-1].first) continue; // 遇到相同的数，只算第一个
        t = y[i][0] + y[n][1] - y[i][1]; // 计算当前阈值下的得分
        // 维护最值
        if(t>=p){
            p=t;
            ans = a[i].first;
        }
    }

    // 输出
    cout << ans;

    return 0;
}