奶牛赛跑

题目描述

输入格式

输出格式

样例

题目描述

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

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

输入格式

• 第一行：三个整数 $N$ ， $L$ 和 $C$ ， $1\leqslant N\leqslant 10^{5}$ ; $1\leqslant L\leqslant 25000$ ; $1\leqslant C\leqslant 25000$

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

输出格式

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

样例

样例输入#1	样例输出#1
4 2 100 20 100 70 1	4

题解

由于题目里面说只要有一头跑完l圈那么所有的牛都会停下来

所以我们可以想给v数组排序（方便后面处理），并算出每头奶牛跑了多少圈（cycle数组）

显然第i头奶牛和第j头奶牛cycle之差下取整

那么题目就简化为给n个实数求每个数与它之前所有数之差下取整的和（n<=1e5显然n^2做法是不可行的，从取值范围可以看出应该是nlogn的）

先举个例子（cycle[i],cycle[j]）=(4.8,5.7) 差的下取整是0 ,但（cycle[i],cycle[j]）=(4.2,5.7) 差的下取整是1，

所以我们可以把cycle分成整数部分cycle，以及小数部分last

若last[i]>last[j],ans=cycle[j]-cycle[i]-1 若last[i]<=last[j],ans=cycle[j]-cycle[i]

所以我们可以在ans里面存下cycle之差然后再在last数组里找逆序对，逆序对有几个ans就得减多少

至于逆序对，我使用归并排序实现（merge为归并排序过程），也可以用树状数组等数据结构（还没写）

详见代码（注意double判断大小的时候用相减判断，不然会出现精度问题，刚开始直接比大小，wa了5个点）

代码

#include<bits/stdc++.h>

using namespace std;

long long i,j,l,m,n,v[100005],ans,c,cycle[100005];

double t,k,last[100005],b[100005];

void merge(int lef,int rig)

{

	if (lef==rig) return;

	if (lef==rig-1)

	{

		if (last[lef]-last[rig]>1e-7) ans--,swap(last[lef],last[rig]);

		return;

	}

	int mid=(lef+rig)/2;

	merge(lef,mid);

	merge(mid+1,rig);

	int i,j,l;

	for (l=i=lef,j=mid+1; i<=mid&&j<=rig;)

	{

		if (last[i]-last[j]>1e-7)

		{

			ans-=(mid-i+1);

			b[l++]=last[j++];

		}

		else b[l++]=last[i++];

	}

	for (; i<=mid;) b[l++]=last[i++];

	for (; j<=rig;) b[l++]=last[j++];

	for (i=lef; i<=rig; i++) last[i]=b[i];

}

int main()

{

	scanf("%lld%lld%lld",&n,&l,&c);

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

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

	t=l*c*1.0/v[n];

	m=0;

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

	{

		cycle[i]=(long long)(t*v[i]/c);

		ans+=(i-1)*cycle[i]-m;

		m+=cycle[i];

		last[i]=t*v[i]-cycle[i]*c;

	}

	merge(1,n);

	printf("%lld",ans);

}

声明：该文章部分摘自这里，若有侵权，请及时联系！

巴特西

【USACO 2012 Open】奶牛赛跑_题解

奶牛赛跑

题目描述

输入格式

输出格式

样例

样例输入#1

样例输出#1

题解

代码

最新文章

热门文章