原题链接：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)
首先了解一下什么是前缀和，前缀和实现原理就是高中的等差数列，忘记的话可以看下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)
原文：https://www.cnblogs.com/z-712/p/14490780.html
