AcWing 3298. 期末预测之最佳阈值
原题链接
中等
作者:
王欢祥
,
2024-12-04 18:10:30
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
int n;
struct predict {
int y;
int res;
} pre[N];
int num0[N], num1[N];
int sum[N];
bool cmp(predict p, predict q) {
if (p.y == q.y)
return p.res < q.res;
return p.y < q.y ;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
pre[i].y = a;
pre[i].res = b;
}
sort(pre + 1, pre + 1 + n, cmp);
num0[1] = 0;
num1[n] = pre[n].res;
for (int i = 2; i <= n; i++) {
if (pre[i - 1].res == 0) {
num0[i] = num0[i - 1] + 1;
} else {
num0[i] = num0[i - 1];
}
}
for (int i = n - 1; i > 0; i--) {
if (pre[i].res == 1) {
num1[i] = num1[i + 1] + 1;
} else {
num1[i] = num1[i + 1];
}
}
//for (int i = 1; i <= n; i++) {
// sum[i] = num0[i] + num1[i];
// cout << pre[i].y << " " << pre[i].res << " " << sum[i] << endl;
//}
int maxindex = pre[1].y, maxsum = num0[1] + num1[1];
for (int i = 2; i <= n; i++) {
if (pre[i].y == pre[i - 1].y)
continue;
else {
if (num0[i] + num1[i] >= maxsum) {
maxindex = pre[i].y;
maxsum = num0[i] + num1[i];
}
}
}
cout << maxindex << endl;
return 0;
}