想要查看其它题解，请点击

题目

一片海域上有一些冰山，第 i 座冰山的体积为 Vi​。

随着气温的变化，冰山的体积可能增大或缩小。第 i 天，每座冰山的变化量都是 Xi​。当 Xi​>0 时，所有冰山体积增加 Xi​；当 <0Xi​<0 时，所有冰山体积减少 −Xi​；当 Xi​=0 时，所有冰山体积不变。

如果第 i 天某座冰山的体积变化后小于等于 00，则冰山会永远消失。

冰山有大小限制 k。如果第 i 天某座冰山 j 的体积变化后 Vj​ 大于 k，则它会分裂成一个体积为 k 的冰山和 Vj​−k 座体积为 11 的冰山。

第 i 天结束前（冰山增大、缩小、消失、分裂完成后），会漂来一座体积为 Yi​ 的冰山（Yi​=0 表示没有冰山漂来）。 小蓝在连续的 m 天对这片海域进行了观察，并准确记录了冰山的变化。

小蓝想知道，每天结束时所有冰山的体积之和（包括新漂来的）是多少。 由于答案可能很大，请输出答案除以 998244353998244353 的余数。

输入描述

输入的第一行包含三个整数n,m,k，分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。

第二行包含 n 个整数 1,2,⋯,V1​,V2​,⋯,Vn​，表示初始时每座冰山的体积。 接下来 m 行描述观察的 m 天的冰山变化。其中第 i 行包含两个整数 Xi​,Yi​，意义如前所述。

输出描述

输出 m 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和除以 998244353998244353 的余数。

我的理解：

就是在一片海域里有冰山，然后该海域里的冰山每天都会增加xi（-k<=xi<=k）,增加后，
        大于k的会分裂为一个体积为k的和（vi-k）个体积为1的
        小于等于0的会消失,

还会漂来一个新冰山（yi<=k）
当每天这些操作结束后，就计算一下所有冰山的总体积。

思路：

如果将所有冰山的体积放入一个列表，那么每天的操作就是给所有冰山增加xi，然后插入一个新冰山yi，然后求一下总和sum，这样做的时间复杂度是O（n）的。

我想到了一种效率更快的方法，维护一个字典，字典的key为体积，value为该体积冰山的数量
        例如 a={1:3,3:2} 就是有3个体积为1的冰山，两个体积为3的冰山
那么这样就不用对每一个冰山都进行操作了，而是对每一类相同体积的冰山进行操作，首先大家应该知道，字典的映射是O（1）的，所以每次分裂出新的冰山与出现新的冰山，我们将他放入字典都是O（1）的，具体的做法如下：

我们将使用两个字典 倒腾着弄，例如a={1:3,3:2}  b={}，xi=2，yi=5, 然后遍历a中的key，每便利一个就加xi，然后插入字典b,最后将yi也插入字典b。

代码实现：

def add(a,k,v):#向字典中插入if k==0:returnif k in a.keys():a[k]+=velse:a[k]=v
n,m,z=map(int,input().split())
arr=[int(i) for i in input().split()]
a={}#key是体积，v是该体积冰山的数量
for i in arr:add(a,i,1)for _ in range(m):xi,yi=map(int,input().split())b={}s=0#求和add(b, yi, 1)one=0#新分裂出的1for k,v in a.items():key=k+xi#旧值加xiif key<=0:#消失continueif key>z:#分裂one+=(key-z)*vkey=zadd(b,key,v)add(b,1,one)for k,v in b.items():#求和s+=k*va=bprint(s%998244353)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！