USACO奶牛赛跑(逆序对)

Description

约翰有 N 头奶牛，他为这些奶牛准备了一个周长为 C 的环形跑牛场。所有奶牛从起点同时起跑，奶牛在比赛中总是以匀速前进的，第 i 头牛的速度为 Vi。只要有一头奶牛跑完 L 圈之后，比赛就立即结束了。

有时候，跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈，从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中，套圈事件一共会发生多少次呢？

Input Format

• 第一行：三个整数 N ，L 和 C，1 ≤ N ≤ 10^5; 1 ≤ L ≤ 25000; 1 ≤ C ≤ 25000

• 第二行到第 N + 1 行：第 i + 1 行有一个整数 Vi，1 ≤ Vi ≤ 10^6

Output Format

单个整数：表示整个比赛过程中，套圈的次数之和

Solution

首先，如果一头牛跑的圈数比另一头牛多，那么它们的差值向下取整即为他们的收益，

容易想到\(O(n^2)\)的做法，枚举每头奶牛与其他奶牛的收益，但这样肯定超时

我们发现，对于一头牛跑的圈数\(cyl[i]\),只要找出所有比他小的值进行处理，

即\(Ans=\sum_{i=1}^nF[i], 且F[i]=\sum \bigg\lfloor cyl[i]-cyl[j]\bigg\rfloor,cyl[i]> cyl[j],1\leq i,j\leq n.\)

但这样好像也没用什么思路，

我们发现，其实\(cyl[i]-cyl[j]\)下取整是因为有小数，而不妨直接先把整数部分直接加起来，然后单独考虑小数部分（好吧也许很难想到）

我们发现，2个数的小数部分最多影响1，如果把cyl数组升序排序，那么Ans只要每次减去前面比当前小数部分小的count即可，

没错！发现变成了求逆序对，那么用树状数组或者归并排序都行

这里采用树状数组，注意离散化

Code

#include <cstdio>

#include <algorithm>

#include <cmath>

#define ll long long

#define db double

#define N 100010

#define lowbit(x) ((x)&(-x))

using namespace std;

const db eps=1e-8;

int n,v[N],L,C,p[N];

ll cyl[N],Ans,m,tree[N];

struct info{

	db num;

	int id;

	friend bool operator < (info a,info b){

		return a.num<b.num;

	}

}A[N];

void add(int x){for(;x<=n;x+=lowbit(x)) tree[x]++;}

ll sum(int x){ll r=0；for(;x;x-=lowbit(x)) r+=tree[x];return r;}

int main(){

	scanf("%d%d%d",&n,&L,&C);

	for(int i=1;i<=n;++i) scanf("%d",&v[i]);

	sort(v+1,v+n+1);

	db t=(db)(L*1ll*C)/(db)v[n];

	for(int i=1;i<=n;++i){

		cyl[i]=(ll)(t*v[i]/C);

		Ans+=(i-1)*cyl[i]-m;

		m+=cyl[i];

		A[i].num=(db)(t*v[i]/C)-(db)cyl[i];

		A[i].id=i;

	}

	sort(A+1,A+n+1);

	int cnt=0;

	for(int i=1;i<=n;++i){

		if(!(fabs(A[i].num-A[i-1].num)<eps)||i==1) ++cnt;

		p[A[i].id]=cnt;

	}

	for(int i=1;i<=n;++i){

		Ans-=sum(n)-sum(p[i]);

		add(p[i]);

	}

	printf("%lld\n",Ans);

	return 0;

}

巴特西