signed

QiShunwang

“诚信为本、客户至上”

CCF CSP202012-2期末预测之最佳阈值

2021/3/21 0:19:37   来源:

CCF CSP202012-2期末预测之最佳阈值

题目背景

考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全,顿顿决定设置一个阈值 θ,以便将安全指数 y 转化为一个具体的预测结果——“会挂科”或“不会挂科”。

因为安全指数越高表明小菜同学挂科的可能性越低,所以当 y≥θ 时,顿顿会预测小菜这学期很安全、不会挂科;反之若 y<θ,顿顿就会劝诫小菜:“你期末要挂科了,勿谓言之不预也。”

那么这个阈值该如何设定呢?顿顿准备从过往中寻找答案。

题目描述

具体来说,顿顿评估了 m 位同学上学期的安全指数,其中第 i(1≤i≤m)位同学的安全指数为 yi,是一个 [0,108] 范围内的整数;同时,该同学上学期的挂科情况记作 resulti∈0,1,其中 0 表示挂科、1 表示未挂科。

相应地,顿顿用 predictθ(y) 表示根据阈值 θ 将安全指数 y 转化为的具体预测结果。
如果 predictθ(yj) 与 resultj 相同,则说明阈值为 θ 时顿顿对第 j 位同学是否挂科预测正确;不同则说明预测错误。
p r e d i c t θ ( y ) = { 0 ( y < θ ) 1 ( y ≥ θ ) predict_θ(y)=\left\{ \begin{aligned} & 0 & (y<θ) \\ & 1 & (y≥θ) \\ \end{aligned} \right. predictθ(y)={01(y<θ)(yθ)

最后,顿顿设计了如下公式来计算最佳阈值 θ∗:
θ ∗ = m a x ( a r g m a x θ ∈ y i ⁡ ∑ j = 1 m ( p r e d i c t θ ( y j ) = = r e s u l t j ) ) θ^∗=max(argmax_{θ∈yi⁡}\sum\limits_{j=1}^{m}(predict_θ(y_j)==result_j)) θ=max(argmaxθyij=1m(predictθ(yj)==resultj))

该公式亦可等价地表述为如下规则:

  1. 最佳阈值仅在 yi 中选取,即与某位同学的安全指数相同;
  2. 按照该阈值对这 m 位同学上学期的挂科情况进行预测,预测正确的次数最多(即准确率最高);
  3. 多个阈值均可以达到最高准确率时,选取其中最大的。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 m。

接下来输入 m 行,其中第 i(1≤i≤m)行包括用空格分隔的两个整数 yi 和 resulti,含义如上文所述。

输出格式

输出到标准输出。

输出一个整数,表示最佳阈值 θ

样例1输入

6
0 0
1 0
1 1
3 1
5 1
7 1

样例1输出

3

样例1解释

按照规则一,最佳阈值的选取范围为 0,1,3,5,7。

θ=0 时,预测正确次数为 4;

θ=1 时,预测正确次数为 5;

θ=3 时,预测正确次数为 5;

θ=5 时,预测正确次数为 4;

θ=7 时,预测正确次数为 3。

阈值选取为 1 或 3 时,预测准确率最高;
所以按照规则二,最佳阈值的选取范围缩小为 1,3。

依规则三,θ=max(1,3)=3。

样例2输入

8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0

样例2输出

100000000

子任务

70% 的测试数据保证 m≤200;

全部的测试数据保证 2≤m≤105

要点分析

方法一:二分法

思路:先将输入分成及格和不及格两类,然后分别排序,再遍历所有备选项,对于每一个备选项,分别利用二分法找到其在两个有序数组中的位置,最后即可求解

代码如下:

#include <bits/stdc++.h>
using namespace std;
//m存储输入的同学数,ans存储最后答案,maxn存储预测正确人数
int m, ans = -1, maxn = -1;
//y0存储实际不及格的人对应的安全指数,y1存储实际及格的人对应的安全指数
int y0[100005], y1[100005];
//ind0表示实际不及格的个数,ind1表示实际及格的个数
int ind0 = 0, ind1 = 0;

//利用二分法求解在y0数组中比x小的有多少个
int f0(int x)
{
	int r = ind0 - 1;
	int l = 0;
	int mid = (r + l) / 2;
	//若x比y0数组中最大的还要大则返回ind0
	if (y0[r] < x)
		return ind0;
	while (r > l)
	{
		mid = (r + l) / 2;
		if (y0[mid] >= x)
			r = mid;
		else
			l = mid + 1;
	}
	return r;
}

//f1函数本质上跟f0的原理一样
//求解在y1数组中比x小的有多少个
int f1(int x)
{
	int r = ind1 - 1;
	int l = 0;
	int mid = (r + l) / 2;
	//若x比y1数组中最大的还要大则返回ind1
	if (y1[r] < x)
		return ind1;
	while (r > l)
	{
		mid = (r + l) / 2;
		if (y1[mid] >= x)
			r = mid;
		else
			l = mid + 1;
	}
	return r;
}
int main()
{
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int y, r;
		cin >> y >> r;
		if (r == 0)
		{
			y0[ind0++] = y;
		}
		else
		{
			y1[ind1++] = y;
		}
	}
	//对两个数组分别进行排序,以便用二分法求解
	sort(y0, y0 + ind0);
	sort(y1, y1 + ind1);
	//分别遍历两个数组中的所有的备选项,找出符合要求的结果
	for (int i = 0; i < ind0; i++)
	{
		//这里tmp是指其对应的预测正确人数,包括其在两个数组中对应的人数
		int tmp = i + ind1 - f1(y0[i]);
		if (tmp >= maxn)
		{
			ans = y0[i];
			maxn = tmp;
		}
	}
	//下面跟上面同理,具体上由于两个数组一个是及格,一个是不及格,略有区别
	for (int i = 0; i < ind1; i++)
	{
		int tmp = ind1 - i;
		for (int j = i - 1; j >= 0; j--)
		{
			if (y1[j] == y1[i])
				tmp++;
			else
				break;
		}
		tmp += f0(y1[i]);
		if (tmp >= maxn)
		{
			ans = y1[i];
			maxn = tmp;
		}
	}
	cout << ans;
}

方法二:前缀和与后缀和

思路:此题对应i位置的预测数量即为排序后的数组中i位置前面(小于)的0的个数以及后面的1的个数之和
代码如下:

#include <bits/stdc++.h>
using namespace std;
//pair数组储存信息,每个pair存储一个同学的y和result
pair<int, int> p[100005];
//pre0记录该位置及前面的result为0的个数(前缀和),rear1记录该位置及后面的result为1的个数(后缀和)
int pre0[100005], rear1[100005];
//ans用来记录最佳阈值,maxn用来记录对应预测正确的数目
int ans = -1, maxn = 0;
int main()
{
	int m;
	cin >> m;
	p[0] = pair<int, int>(-1, -1);
	for (int i = 1; i <= m; ++i)
		cin >> p[i].first >> p[i].second;
	//将所有学生信息按照阈值从小到大排序,便于后续求前缀,后缀和
	sort(p + 1, p + 1 + m);
	//记录前缀0个数
	for (int i = 1; i <= m; ++i) 
		if (p[i].second == 0)
			pre0[i] = pre0[i - 1] + 1;
		else
			pre0[i] = pre0[i - 1];
	//记录后缀1个数
	for (int i = m; i >= 1; --i) 
		if (p[i].second == 1)
			rear1[i] = rear1[i + 1] + 1;
		else
			rear1[i] = rear1[i + 1];
	for (int i = 1; i <= m; ++i)
	{
		if (maxn <= pre0[i - 1] + rear1[i])
			maxn = pre0[i - 1] + rear1[i];
			ans = p[i].first;
	}
	cout << ans;
	return 0;
}