[CSP]202012-2期末预测之最佳阈值

题目

• 样例1：

输入
6
0 0
1 0
1 1
3 1
5 1
7 1

输出
3

• 样例2

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

输出
100000000

题解

原来顺着题意走，先用set存储各个阈值，再在各个阈值下计算预测正确的个数
这样就有了双层循环，导致超时

可以观察到，随着阈值的增加，通过（re=1）的值是在不断减小的，未通过则增加，其是有一定规律的
若按上面直接逐一统计，会出现许多重复计算
则可以尝试先算出整体通过、未通过的数量，阈值增加则增或减响应数量来达到统计正确率的目的

详细讲解在注释

m = int(input())
p,n = 0,0  # 先找出所有通过与不通过的数
result,theta = [],[]
for i in range(m):
    y,score = map(int,input().split())
    if score:  p+=1  # 统计所有通过的
    else: n+=1       # 统计所有未通过的
    result.append([y,score])
result = sorted(result)
p1=p     # p1记录在当前分数线下通过的数量
j = -1   # 分数线数组theta的游标
for i in range(m): # 先正着计算，后面比她大的都是通过的，每遇到一个通过的就少一个
    if i==0:    # 第一个值先直接放入（第一个遇到的，作阈值）
        theta.append([result[i][0],p1]) # 第一个元素，直接放入
        j+=1    # theta游标+1
    elif result[i][0] != result[i-1][0]:   # 出现新阈值（分数不一样才作为新分割线）
        theta.append([result[i][0],p1])    # 以该元素为起点，后面是比他高的，则分类正确的数量为p1
        j+=1
    if result[i][1]: p1-=1  # 每路过一个通过的值，就会少一个
n1 = n
# 再从后向前，看分数线前没通过的值，也是判断正确的
for i in range(m-1,-1,-1):
    ''' 注意： 因为>=分数线都是通过，所以上面处理通过时先存入再减去 而分数线下，<就是不通过，不能等于，所以要先处理 '''
    if not result[i][1]:  n1 -= 1 # 走过一个为通过的，就少一个
    if result[i][0] != result[i-1][0]: # 遇到新阈值
        theta[j][1]+=n1                # 小于阈值的，未通过的值为n1，也是正确的
        j-=1                           # theta前进一个（下一个阈值）
print(sorted(theta,key = (lambda x:x[1]))[-1][0])  # 按正确率排序（都一样再按数值升序）
# 取最后一个数据输出