?202012-2 期末预测之最佳阈值

注意: 1、暴力破解会超时 2、前缀和、后缀和 问题描述
试题编号: 202012-2
试题名称: 期末预测之最佳阈值
时间限制: 1.0s
内存限制: 512.0MB
问题描述:

题目背景

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

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

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

题目描述

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

相应地,顿顿用 predictθ(y) 表示根据阈值 θ 将安全指数 y 转化为的具体预测结果。
如果 predictθ(yj) 与 resultj 相同,则说明阈值为 θ 时顿顿对第 j 位同学是否挂科预测正确;不同则说明预测错误。

predictθ(y)={0(y<θ)1(y≥θ)

最后,顿顿设计了如下公式来计算最佳阈值 θ∗:

θ∗=maxargmaxθ∈yi⁡∑j=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
Data

样例1输出

3
Data

样例1解释

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

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

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

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

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

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

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

依规则三,θ∗=max1,3=3。

样例2输入

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

样例2输出

100000000
Data

子任务

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

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

 

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

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int M = 100000;
pair<int, int> a[M + 1];
int prefix[M + 2], suffix[M + 2], p[M + 2];

int main()
{
    int m, i;

    scanf("%d", &m);
    for(i = 1; i <= m; i++)
        scanf("%d%d", &a[i].first, &a[i].second);

    sort(a + 1, a + 1 + m);

    // 前缀和
    prefix[0] = 0;
    for(i = 1; i <= m; i++)
        prefix[i] = prefix[i - 1] + (a[i].second == 0 ? 1 : 0);
    // 后缀和
    suffix[m + 1] = 0;
    for(i = m; i >= 1; i--)
        suffix[i] = suffix[i + 1] + (a[i].second == 1 ? 1 : 0);

    int pos = 1;
    p[1] = 1;
    for(i = 1; i <= m; i++)
        if(a[i].first == a[i - 1].first)
            p[i] = pos;
        else
            p[i] = (pos = i);

    int ans = 0, mx = 0;
    for(i = 1; i <= m; i++) {
        int cur = prefix[p[i] - 1] + suffix[i];
        if(cur >= mx)
            mx = cur, ans = a[i].first;
    }

    printf("%d\n", ans);

    return 0;
}

  

上一篇:Oracle迁移到MySQL性能下降的注意点(转)


下一篇:Udesk全场景客服系统FAQ分享(202012期)