CSP 202112-2 序列查询新解 python 离散+二分法
题目描述
思路
思路大概是离散化+二分法，我们可以看到测试的规模，如果利用暴力法，我们只能过70%样例，最后获得70%的分，所以不能直接用暴力的方法
考虑用N太浪费时间，发现如果用n进行循环，时间就不会超出限制，又能够发现A[i-1]~A[i]内f的值都是一样的，所有的g的值其实就是i/r的整数部分，因此一开始想到把全部的f的值加起来，g的值加起来作差就行，但最后发现不对，因为中间有些做完差后需要取绝对值
就考虑在已经分好的 A[i-1]~A[i]区间内再去找哪一部分大于g（这里由前面推论可知g的值和i有关，因此分别求出左右两端的区间端点g值判断划分即可）,然后再以r为区间长度进行循环求解，得出答案。
代码
# http://118.190.20.162/submitlist.page?gpid=T137 # 输入的数据 n,N = map(int,input().split()) A = [0] A.extend(list(map(int,input().split()))) A.append(N) r = N // (n+1) B = [] for i in range(N//r + 2): if i*r >= N: break B.append(i*r) B.append(N) s = list(set(A+B)) s.sort() L = len(s) # 离散化 tree = [0]*(L-1) from bisect import bisect_left as bl for i in range(len(A) - 1): a,b = bl(s,A[i]),bl(s,A[i+1]) for j in range(a,b): tree[j] += i for i in range(len(B) - 1): a,b = bl(s,B[i]),bl(s,B[i+1]) for j in range(a,b): tree[j] -= i # tree求两边的差值的划分 ans = 0 for i in range(L-1): # tree[i]代表的是差值，s[i+1] - s[i]代表的是区间的长度 ans += abs(tree[i]*(s[i+1]-s[i])) print(ans)
