2012年暑期集训(新队员组)―综合赛7解题报告

关于Running laps的思考-by ahmasoi

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!若要更好的方法请拿出来分享啊!!


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.