解题思路:前缀和、差分的综合使用比如求区间和,在某个区间都加上1,不建议求更新数组后的和使再次使用前缀和求区间和,因为会多几次循环会超时,建议直接元素相乘可以少几次循环即可AC 代码有详细注释
注意事项: 就是m的输入和数组元素的输入在同一行所以会显示运行错误 正常是m在数组元素的下一行
参考代码:
n=int(input())
a=[0]+list(map(int,input().split()))
m=int(input())
v=[0]*(n+2)#vt的差分数组 多开一个位置防止越界
vt=[0]*(n+2)
sum=[0]*(n+1)
ans=[0]*(n+1)
sum1=0
sum2=0
b=[]
for i in range(1,len(a)):#前缀和
sum[i]=sum[i-1]+a[i]
for i in range(m):
b.append(list(map(int,input().split())))
l,r=b[i][0],b[i][1]
sum1+=sum[r]-sum[l-1]#前缀和求区间和
v[l]+=1
v[r+1]-=1#差分打标记
for i in range(1,len(v)):
vt[i]=vt[i-1]+v[i]
a.sort ()#求sum2就不用前缀和了会多用两次循环超时,那么直接相乘就好了:次数*数值
vt.sort()
for i in range(len(vt)-1,-1,-1):
sum2+=a[i-1]*vt[i]
print(sum2-sum1)
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)scanf后面加个getchar(),收掉回车符,就可以用gets了浏览:1149 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:542 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:688 |
C语言考试练习题_排列 (C++代码)浏览:638 |
钟神赛车 (C++代码)浏览:866 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:551 |
蛇行矩阵 (C语言代码)浏览:752 |
1009题解浏览:750 |
1011题解浏览:765 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:556 |