JZOJ 3.10 1542——跑步（树状数组+模拟+排序/归并排序）

题目描述

FJ觉得赛马很无聊，于是决定调查将赛牛作为一种运动的可能性。他安排了N(1 <= N <= 100,000)头奶牛来进行一个L圈的赛牛比赛，比赛在一个环形的长度为C的跑道上进行。所有的奶牛在跑道上的同一个点出发，每头奶牛的速度不同，当最快的奶牛跑完L*C的距离后结束。

FJ注意到了一头奶牛超过另一头奶牛这种情况的发生，并且他想知道这种“超车事件”在整个比赛中发生了多少次。更明确地，一次超车事件被定义为一对奶牛(x, y)和一个时刻t（小于等于结束时刻），且t时刻奶牛x超越到了奶牛y的前面，请帮助FJ计算整个比赛过程中“超车事件”发生的次数。

输入

第1行，3个空格隔开的整数N、L、C(1 <= L,C <= 25,000)

第2行至第n + 1行，第i + 1行有一个整数，表示第i个奶牛的速度，范围在1..1000000之间

输出

超车总数

样例输入

4 2 100

20

100

70

1

样例输出

4

---

① 我终于懂得了C++的美好！
首先找出速度最快的奶牛——Max
然后就可以如果求出最快的奶牛跑完，这头奶牛可以跑多少圈。公式即为l*c/max*S/c，约分后得l*s/max，将小数和整数分开存。
快排一遍，从大到小排。
最后我们，求出求出最多的超车数，用树状数组维护。

---

---

②用归并排序方能ACE也
我们可以先快排一遍
像方法一一样，现将小数部分和整数部分先求出来。
然后当做没有小数去做，求出超车数。
再回过来做小数部分，如果像上面一样再排一遍再做的话o(2n)因该会超时（我没试过，有兴趣的朋友可以试一试，然后在留言区噪起来吧）
如果这样，就可以使用归排。方可ACE可！！！！！！！！！！！

---

①

代码如下：

#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; long long n,m,l,c,q[100002],Max,h,ans,sz[1000002]; typedef struct{long long s,t; }P; bool cmp(P aa,P bb) {if (aa.s!=bb.s)return aa.s<bb.s;return aa.t<bb.t; } P p[100002]; long long chaxun(long long x) {int ans=0;for (;x>=1;x-=x&-x)ans+=sz[x];return ans; } void gengxin(long long x) {for (;x<=m;x+=x&-x)sz[x]++; } int main() {freopen("running.in","r",stdin);freopen("running.out","w",stdout);scanf("%lld%lld%lld",&n,&l,&c);m=1e6;for (int i=0;i<n;i++){scanf("%lld",&q[i]);Max=max(Max,q[i]);}for (int i=0;i<n;i++){p[i].s=q[i]*l/Max;p[i].t=q[i]*l%Max;}sort(p,p+n,cmp);for (int i=0;i<n;i++){ans+=i*p[i].s-h-(chaxun(m)-chaxun(p[i].t));h+=p[i].s;if (p[i].t)gengxin(p[i].t);}printf("%lld",ans);return 0; }

②

代码如下：

var ans,count,w:int64;v,s:array[0..100001]of longint;t,r:array[0..100001]of extended;i,j,n,x,y,l,c:longint;m,d:extended;procedure qsort(l,r:longint); var i,j,mid:longint; beginif l>=r then exit;i:=l; j:=r; mid:=v[i];repeatwhile v[i]>mid do inc(i);while v[j]<mid do dec(j);if i<=j thenbeginv[0]:=v[i];v[i]:=v[j];v[j]:=v[0];inc(i);dec(j);end;until i>j;qsort(l,j);qsort(i,r); end;procedure gb(x,y:longint); var i,j,k,mid:longint; beginif x=y then exit;mid:=(x+y) div 2;gb(x,mid);gb(mid+1,y);i:=x;j:=mid+1;k:=x;while (i<=mid) and (j<=y) dobeginif t[i]-t[j]>-0.0000001 thenbeginr[k]:=t[i];inc(i);inc(k);endelsebeginr[k]:=t[j];inc(j);inc(k);w:=w+mid-i+1;end;end;while i<=mid dobeginr[k]:=t[i];inc(i);inc(k);end;while j<=y dobeginr[k]:=t[j];inc(j);inc(k);end;for i:=x to y do t[i]:=r[i]; end;beginassign(input,'running.in');assign(output,'running.out');reset(input);rewrite(output);readln(n,l,c);for i:=1 to n do readln(v[i]);qsort(1,n);m:=(l*c)/v[1];ans:=0;count:=0;for i:=1 to n dobegind:=v[i]*m;s[i]:=trunc(d/c);l:=s[i]*c;t[i]:=d-l;end;for i:=n downto 1 dobegincount:=count+(n-i)*(s[i]-s[i+1]);ans:=ans+count;end;w:=0;gb(1,n);write(ans-w);close(input);close(output); end.

转载于:https://www.cnblogs.com/Comfortable/p/8412368.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的JZOJ 3.10 1542——跑步（树状数组+模拟+排序/归并排序）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。