期末预测之最佳阈值
题目描述
具体来说，顿顿评估了
m
m
m位同学上学期的安全指数，其中第
i
(
1
≤
i
≤
m
)
i(1\le i\le m)
i(1≤i≤m)位同学的安全指数为
y
i
y_i
yi，是一个
[
0
,
1
0
8
]
[0,10^8]
[0,108]范围内的整数；同时，该同学上学期的挂科情况记作
r
e
s
u
l
t
i
∈
{
0
,
1
}
result_i\in \{0,1\}
resulti∈{0,1}，其中
0
0
0表示挂科、
1
1
1表示未挂科。
相应地，顿顿用
p
r
e
d
i
c
t
θ
(
y
)
predict_{\theta}(y)
predictθ(y)表示根据阈值
θ
\theta
θ将安全指数
y
y
y转化为的具体预测结果。 如果
p
r
e
d
i
c
t
θ
(
y
j
)
predict_{\theta}(y_j)
predictθ(yj)与
r
e
s
u
l
t
j
result_j
resultj相同，则说明阈值为
θ
\theta
θ时顿顿对第
j
j
j位同学是否挂科预测正确；不同则说明预测错误。
p
r
e
d
i
c
t
θ
(
y
)
=
{
0
(
y
<
θ
)
1
(
y
≥
θ
)
predict_{\theta}(y)=\begin{cases}0&(y\lt \theta)\\1&(y\ge \theta)\end{cases}
predictθ(y)={01(y<θ)(y≥θ)
最后，顿顿设计了如下公式来计算最佳阈值
θ
∗
\theta^*
θ∗
θ
∗
=
max
arg max
θ
∈
y
i
∑
j
=
1
m
(
p
r
e
d
i
c
t
θ
(
y
j
)
=
=
r
e
s
u
l
t
j
)
\theta^*=\max \argmax\limits_{\theta\in y_i}\sum\limits_{j=1}^{m}(predict_{\theta}(y_j)==result_j)
θ∗=maxθ∈yiargmaxj=1∑m(predictθ(yj)==resultj)
该公式亦可等价地表述为如下规则：
最佳阈值仅在
y
i
y_i
yi中选取，即与某位同学的安全指数相同；
按照该阈值对这
m
m
m位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）；
多个阈值均可以达到最高准确率时，选取其中最大的。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数
m
m
m。
接下来输入
m
m
m行，其中第
i
(
1
≤
i
≤
m
)
i(1\le i\le m)
i(1≤i≤m)行包括用空格分隔的两个整数
y
i
y_i
yi和
r
e
s
u
l
t
i
result_i
resulti，含义如上文所述。
输出格式
输出到标准输出。
输出一个整数，表示最佳阈值
θ
∗
\theta^*
θ∗。
样例1输入
6
0 0
1 0
1 1
3 1
5 1
7 1
样例1输出
3
样例1解释
按照规则一，最佳阈值的选取范围为
0
,
1
,
3
,
5
,
7
0,1,3,5,7
0,1,3,5,7。
θ
=
0
\theta=0
θ=0时，预测正确次数为
4
4
4；
θ
=
1
\theta=1
θ=1时，预测正确次数为
5
5
5；
θ
=
3
\theta=3
θ=3时，预测正确次数为
5
5
5；
θ
=
5
\theta=5
θ=5时，预测正确次数为
4
4
4；
θ
=
7
\theta=7
θ=7时，预测正确次数为
3
3
3。
阈值选取为
1
1
1或
1
1
1时，预测准确率最高； 所以按照规则二，最佳阈值的选取范围缩小为
1
,
3
1,3
1,3。
依规则三，
θ
∗
=
max
{
1
,
3
}
=
3
\theta^*=\max\{1,3\}=3
θ∗=max{1,3}=3。
样例2输入
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
样例2输出
100000000
子任务
70
%
70\%
70%的测试数据保证
m
≤
200
m\le 200
m≤200；
全部的测试数据保证
2
≤
m
≤
1
0
5
2\le m\le 10^5
2≤m≤105。
思路
注意到此题可以化简思路：对于数组
a
a
a中的每个值
k
e
y
key
key，求出在
r
e
s
u
l
t
∈
{
0
,
1
}
result\in \{0, 1\}
result∈{0,1}时，
y
≥
k
e
y
y\ge key
y≥key和
y
<
k
e
y
y\lt key
y<key的元素个数。
暴力法：
当
k
e
y
key
key只有一个值时，很容易查找，只需要遍历一遍数组即可解决，所以暴力法的思路是对每个
k
e
y
key
key进行枚举。
两层循环，外循环枚举每一个值，内循环遍历每一个数据判断是否满足
p
r
e
d
i
c
t
=
=
r
e
s
u
l
t
predict==result
predict==result，进行了两层循环，时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
数据量到了
1
0
5
10^5
105级别，
O
(
n
2
)
O(n^2)
O(n2)显然时间会爆掉。
优化算法
一般
1
0
5
10^5
105数据量都会用
O
(
n
log
n
)
O(n\log n)
O(nlogn)的时间复杂度，所以考虑排序算法。
排序后有两个问题：
-
r
e
s
u
l
t
=
0
result=0
result=0和
r
e
s
u
l
t
=
1
result=1
result=1处理方式不同，所以将两种情况单独存储，将
r
e
s
u
l
t
=
0
result=0
result=0和
r
e
s
u
l
t
=
1
result=1
result=1的数据用两个
v
e
c
t
o
r
vector
vector分开存储。
- 排序完的操作：采用二分查找即可
排序的时间复杂度为
O
(
n
log
n
)
O(n\log n)
O(nlogn)，对每个元素枚举后进行一次二叉查找为
O
(
n
log
n
)
O(n\log n)
O(nlogn)，则时间复杂度为
O
(
n
log
n
)
O(n\log n)
O(nlogn)
#include <bits/stdc++.h>
using namespace std;
vector<int> a[2];
int ans, m, x, y, val;
int main() {
scanf("%d", &m);
for(int i = 1; i <= m; i++) scanf("%d %d", &x, &y), a[y].push_back(x);
for(int i = 0; i < 2; i++) sort(a[i].begin(), a[i].end());
for(int i = 0; i < 2; i++) {
int len = a[i].size();
for(int j = 0; j < len; j++) {
int s = (lower_bound(a[0].begin(), a[0].end(), a[i][j]) - a[0].begin()) + (a[1].size() - (lower_bound(a[1].begin(), a[1].end(), a[i][j]) - a[1].begin()));
if(s > val || (s == val && a[i][j] > ans)) {
val = s;
ans = a[i][j];
}
}
}
printf("%d", ans);
return 0;
}
前缀和做法
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
unordered_map<int, bool> ext;
pair<int, int> a[maxn];
int n, x, y, s[maxn], ans, Max;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d %d", &x, &y), a[i] = make_pair(x, y);
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i].second;
for(int i = 1; i <= n; i++) {
if(ext[x = a[i].first]) continue;
ext[x] = true;
int val = s[n] + i - 1 - 2 * s[i - 1];
if(val >= Max) {
Max = val;
ans = x;
}
}
printf("%d", ans);
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
