CCF202012-Python题解

期末预测之安全指数

试题编号：	202012-1
试题名称：	期末预测之安全指数
时间限制：	1.0s
内存限制：	512.0MB

2
-10 100
-1 15

 1 n=int(input())
 2 summ=0
 3 for _ in range(n):
 4     s,w=map(int,input().split())
 5     summ+=(s*w)
 6 
 7 if summ>=0:
 8     print(summ)
 9 else:
10     print(0)

期末预测之最佳阈值

原题链接：http://118.190.20.162/view.page?gpid=T122

70分超时代码，当m=10e^5 这表示着这题暴力两层for循环是没有出路的

 1 n=int(input())
 2 ans=[list(map(int, input().split())) for _ in range(n)]
 3 
 4 summ=[]
 5 maxx=0
 6 a=[]
 7 for i in range(n):
 8     tmp=ans[i][0]
 9     if tmp not in a:
10         num=0
11         for j in range(n):
12             if ans[j][0]>=tmp and ans[j][1]==1:
13                 num+=1
14             elif ans[j][0]<tmp and ans[j][1]==0:
15                 num+=1
16         if num>=maxx:
17             maxx=num
18             summ.append([num,ans[i][0]])
19         a.append(tmp)
20 find=0
21 
22 for i in range(len(summ)):
23     if summ[i][0]==maxx:
24         if summ[i][1]>find:
25             find=summ[i][1]
26     
27 print(find)

View Code

首先了解一下什么是前缀和，前缀和实现原理就是高中的等差数列，忘记的话可以看下b站讲解或者刷下LeetCode560

在排序完以后，这题就是统计在（0的个数）当前位置（1的个数）

import sys
n=int(input())
arr=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
summ=[0 for i in range(n+1)]
listArr=sorted(arr,key=lambda x:x[0])
redu=set() #去重，减少循环次数
for i in range(1,n+1):
    summ[i]=summ[i-1]+listArr[i-1][1]

target=-1
find=-1

for i,pair in enumerate(listArr):
    if pair[0] in redu:
        continue
    redu.add(pair[0])
    one=summ[n]-summ[i]#总共为1的个数-从1到i为1的个数
    zero=i-summ[i]#减去比当前i小的值还为1的数
    total=zero+one
    if total>=target:
        target=total
        find=pair[0]

print(find)