[USACO 2012 Open]Running Laps奶牛赛跑

题目链接：~~找不到QWQ~~http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4074

[在一个并没有去过的oj找到了orzorzorz那是人家学校自己的oj?

题目大意：

题解：

树状数组

因为同一起跑线同一时间，所以根据速度排个序先是显而易见的啦。

先讲下O(n^2)，所求的答案就是两两判断一个比另一个跑多了几圈。p.s.一定要去尾取整，因为不到一圈是还没超过的。

因为范围，这样做会超时。但是如果先把每只牛能跑的圈数算出来。

例如样例，每只牛分别跑了：0.02，0.4，1.4，2圈。设圈数为Qi

那么按顺序扫下来，第i只牛对答案的贡献就是sigema{ [Qi] - [Qj] - ( (Qi-[Qi])≥(Qj-[Qj]) )? 0:1 },1≤j<i。

把式子拆成整数部分([Qi])+小数部分(Qi-[Qi])分别用树状数组来做就好了√ ([x]表示向下取整

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
#define maxn 101000

const LL mxn=100000;
struct node
{
	LL id,x,ls;double y;//x-整数部分 y-小数部分 ls-小数的离散值
}ss[maxn];
LL r[maxn],v[maxn];
LL lowbit(LL x){return x&(-x);}
void ins(LL x,LL y) {for (x;x<=mxn;x+=lowbit(x)) r[x]+=y;}
LL ask(LL x)
{
	LL ret=0;
	for (;x>0;x-=lowbit(x)) ret+=r[x];
	return ret;
}
bool cmp1(node x,node y) {return x.y<y.y;}
bool cmp2(node x,node y) {return x.id<y.id;}
int main()
{
	//freopen("running.in","r",stdin);
	//freopen("running.out","w",stdout);
	LL n,m,c,i,ans;
	scanf("%I64d%I64d%I64d",&n,&m,&c);
	for (i=1;i<=n;i++) scanf("%I64d",&v[i]);
	sort(v+1,v+1+n);ans=0;
	memset(r,0,sizeof(r));
	for (i=1;i<=n;i++)//分离小数&整数部分
	{
		double orz=1.0*m*v[i]/v[n];
		ss[i].y=(double)(orz-(m*v[i]/v[n]));
		ss[i].x=orz-ss[i].y;
		ss[i].id=i;
		ans+=(i-1)*ss[i].x-ask(i);//算整数部分的答案,不管是否真的够一圈都先算了
		ins(i,ss[i].x);
	}sort(ss+1,ss+1+n,cmp1);
	LL p=1;ss[1].ls=1;//对小数部分离散化
	for (i=2;i<=n;i++)
	 if (abs(ss[i].y-ss[i-1].y)<0.000001) ss[i].ls=p;
	 else ss[i].ls=++p;
	sort(ss+1,ss+1+n,cmp2);
	memset(r,0,sizeof(r));
	for (i=1;i<=n;i++)//算小数那部分的
	{
		ans-=(i-1)-ask(ss[i].ls);//把真的相差不够一圈的减掉
		ins(ss[i].ls,1);
	}printf("%I64d
",ans);
	return 0;
}

终于。。完了！复习初赛去！还什么都不会啊QwQ