AcWing 3298. 期末预测之最佳阈值csp21(2)
原题链接
中等
作者:
YAX_AC
,
2024-12-05 20:30:21
,
所有人可见
,
阅读 8
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
int n;
PII q[N];
int s[2][N];
int main()
{
cin>>n;
for(int i = 1; i<=n; i++) cin>>q[i].x>>q[i].y;
sort(q+1,q+n+1);
for(int i = 0; i<2; i++)
for(int j = 1; j<=n; j++)
s[i][j] = s[i][j-1]+(q[j].y == i);
int cnt = -1,res = 0;
for(int i = 1; i<=n; i++)
{
int t = s[0][i-1]+s[1][n]-s[1][i-1];
if(t>=cnt) cnt = t,res = q[i].x;
//两个相同的q[].x不能划线
while(i+1<=n && q[i+1].x == q[i].x) i++;
}
cout<<res;
return 0;
}