AcWing 3298. 期末预测之最佳阈值
原题链接
中等
作者:
Value
,
2021-04-08 19:50:17
,
所有人可见
,
阅读 390
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1E5 + 10;
typedef pair<int, int> pii;
pii a[N];
int s[2][N];
int main(){
int n; cin >> n;
for(int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i].first, &a[i].second);
sort(a + 1, a + 1 + n);
for(int i = 0; i < 2; i ++ )
for(int j = 1; j <= n; j ++ )
s[i][j] = s[i][j - 1] + (a[j].second == i);
int maxv = -1, res;
for(int i = 1; i <= n; i ++ ){
int sum = s[0][i - 1] + s[1][n] - s[1][i - 1];
if(sum >= maxv) maxv = sum, res = a[i].first;
while(a[i].first == a[i + 1].first) i ++ ;
}
cout << res << endl;
return 0;
}