AcWing 3298. 期末预测之最佳阈值
原题链接
中等
作者:
把这题Ac了
,
2024-12-07 10:54:22
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int,int> PII;
struct node{
int l,r;
}q[N];
int a[N],b[N];
int n;
bool cmp(node &a,node &b){
if(a.l != b.l) return a.l < b.l;
return a.r < b.r;
}
int main(){
cin >> n;
for(int i = 1;i <= n;i++){
cin >> q[i].l >> q[i].r;
}
sort(q + 1,q + n + 1,cmp);
for(int i = 1;i <= n;i++){
if(q[i].r){
b[i] = b[i - 1] + 1;
a[i] = a[i - 1];
}
else{
a[i] = a[i - 1] + 1;
b[i] = b[i - 1];
}
}
int res = -1,tt = 0;
int s = q[1].l,cnt = 0;
for(int i = 1;i <= n;i++){
int t = q[i].l;
int x = cnt;
if(t < s && !q[i].r) cnt++;
if(t >= s && q[i].r) cnt++;
res = max(res,cnt);
}
tt = s;
int m1,m2 = 0;
int p = 0;
for(int i = 1;i <= n;i++){
int j = i + 1;
while(j <= n && q[j].l == q[1].l) j++;
p = j;
m1 = b[j - 1] - b[i - 1];
m2 = a[j - 1] - a[i - 1];
break;
}
for(int i = p;i <= n;i++){
int s1 = q[i - 1].l,t1 = q[i - 1].r;
int s2 = q[i].l,t2 = q[i].r;
if(!t1 || m2){
if(m2){
cnt += m2;
m2 = 0;
}
else cnt ++;
}
if(t1 || m1){
if(m1){
cnt -= m1;
m1 = 0;
}
else cnt --;
}
int j = i + 1;
while(j <= n && q[j].l == s2) j++;
if(j != i + 1){
m1 = b[j - 1] - b[i - 1];
m2 = a[j - 1] - a[i - 1];
i = j - 1;
}
if(res <= cnt){
res = cnt;
tt = max(s2,tt);
}
}
cout << tt << endl;
return 0;
}