自动搬运

查看原文

来自洛谷，原作者为

	simonG 去做你认为对的

搬运于2025-08-24 21:44:49，当前版本为作者最后更新于2020-12-14 14:05:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

由于蒟蒻不会线段树，或者是树状数组，
暴力法可以得到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)$。
  所以，需要用归并排序，一种非常简便的方法，求出逆序对的个数。

代码

$O(n*logn)$算法，如下

#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;
}

后记

记录

遇到难题时，不一定要考虑非常高级的算法，从最简单的开始，逐步往上推，直至最优解。