E:Running Laps
本题感觉自己的思路正确,只是时间和空间复杂度有些高,还请大家能讨论出更有效的算法!!
先按速度从小到大排序,然后求出每个人所跑的圈数和剩余的部分(按a[i]*l 与 a[n-1]求整除(存放于a[i])和求余(存放地b[i])两部分,这样保证数据是整型,也是为了后面线段树使用)
然后把剩余部分以线段数方式来保存,按上面的排过序的顺序一边处理一边把剩余部分添加到线段数中。
我们来讨论一下第i个所能形成的套圈数该怎么计算!!我们先看第i个与第k个形成套圈的情况:(1)a[i]>a[k]+1,必然形成套圈!(2)a[i]=a[k]+1,此时当b[i]>=b[k]也会形成套圈!(3)当a[i]=a[k]时,由于排过序,所以此时必然有b[i]>=b[k],且不能形成套圈!。
现在知道了套圈的情况,那如何来计算套圈数呢?首先套圈数<=a[i]-a[k],当b[i]>=b[k]时,为a[i]-a[k],当b[i]<b[k]时,为a[i]-a[k]-1;
这样我们就知道了,套圈数为a[i]-a[k]-(b[i]<b[k])
所以对于第i个,套圈数为i*a[i]-sum(a[k]{k=1..i-1}) - sum(b[i]<b[k]{k=1..i-1})
把这个和为成两个部分,前面一部分就和比较简单!
后面一部分就可以利用线段树来求出比b[i]大的的个数即可!
这里的空间复杂度为o(2*M),即以剩余部分作线段数的空间,时间复杂度为:o(n*ln(m)+ln(n)),即快排的时间和对每个点修改和查询线段数时间。
偶过的有些险,空间39M时间855ms!若要更好的方法请拿出来分享啊!!