题解 P3054

· · 题解

前言

由于蒟蒻不会线段树，或者是树状数组，
暴力法可以得到12分（O(n*n)）。

所以我们需要一种非常简单的算法，也就是归并，时间复杂度为O(n*logn)。而且易于理解

详解

  • 1, 我们知道，超越次数=（int）圈数之差
    求出每一头牛在结束时跑了的圈数。我们假定，圈数在整数的情况下，例如
    1,2,3

    2-1+3-2+3-1=4

    总共4次超越
    但是，只是应用于整数的情况下

  • 2, 所以我们需要考虑精度的问题，然后标记。最后，剩下的整数部分就是求逆序对（求差）的过程。逆序对减去之前标记的就是答案。
    1.3,2.8,3.2
    在整数情况下还是4次，但是看下例

    int(2.8-1.3)+int(3.2-2.8)+int(3.2-1.3)=1+0+1=2

    显然不一样了，只有2次。

  • 3, 我们一个一个枚举圈数之间的差，需要两层for遍历，时间复杂度为 O(n*n)。
    所以，需要用归并排序，一种非常简便的方法，求出逆序对的个数。

代码

```cpp #include<bits/stdc++.h>//万能头文件 #define ll long long//不开longlong见祖宗 using namespace std;//命名空间 #define maxn 100003//数据范围 ll n,l,c; ll V[maxn];//速度 ll d[maxn],a[maxn],f[maxn],s[maxn]; inline ll read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } //快-读 ll Msort(ll l,ll r) { //归并排序 if(l>=r)return 0;//递归边界 ll ans=0; int mid=(l+r)>>1;//(l+r)/2 ans+=Msort(l,mid); ans+=Msort(mid+1,r); for(int i=l; i<=mid; i++) a[i]=d[i]; for(int i=mid+1,j=r; j>=mid+1; i++,j--) a[i]=d[j]; int i=l; int j=r;//左右边界 for(int k=l; k<=r; k++) if(a[i]<=a[j]) d[k]=a[i++]; else { ans+=mid-i+1;//求逆序对 d[k]=a[j--]; } return ans;//逆序对个数 } int main(){ n=read(),l=read(),c=read();//读入 for(int i=1; i<=n; i++) V[i]=read();//读入 sort(V+1,V+n+1);//有序性 ll ans=0,t=0; for(int i=1; i<=n; i++) { f[i]=l*V[i]/V[n]; d[i]=l*V[i]%V[n]; }//圈数，个数 for(int i=1; i<=n; i++) { ans+=(i-1)*f[i]-t; t=t+f[i]; } //枚举 ans-=Msort(1,n);//减去逆序对个数 printf("%lld",ans);//输出 return 0; } ``` ### 后记 [记录](https://www.luogu.com.cn/record/43805109) 遇到难题时，不一定要考虑非常高级的算法，从最简单的开始，逐步往上推，直至最优解。