比赛 noip 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __卡片游戏 最终得分 100
用户昵称 . 运行时间 5.299 s
代码语言 C++ 内存使用 7.55 MiB
提交时间 2016-11-04 21:47:14
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int mxn=500010;
int a[mxn],r[mxn],n,s[mxn],t[mxn];
ll sum;
double k;

bool cp(const int x,const int y){
	double x1=k*x-s[x],y1=k*y-s[y];
	return x1<y1||(x1==y1&&x<y);
}
void ms(int L,int R){
	if(L>=R) return;
	int mi=(L+R)/2,p,q,i;
	ms(L,mi); ms(mi+1,R);
	i=L; p=L; q=mi+1;
	while(p<=mi||q<=R){
		if(q>R||(p<=mi&&r[p]<r[q])){
			sum+=R-q+1;
			t[i++]=r[p++];
		}
		else t[i++]=r[q++];
	}
	for(i=L;i<=R;i++) r[i]=t[i];
}
void sol(){
	for(int i=0;i<=n;i++) r[i]=i;
	sort(r,r+1+n,cp);
	sum=0;
	ms(0,n);
}
ll gcd(ll a,ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	freopen("xgame.in","r",stdin);
	freopen("xgame.out","w",stdout);
	int i,l,r;
	ll c,b,g;
	scanf("%d%d%d",&n,&l,&r);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	s[0]=0;
	for(i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	k=r;
	sol(); c=sum;
	k=l-0.000001;
	sol(); c-=sum;
	b=(ll)n*(n+1)/2;
	if(c==0){ printf("0\n"); return 0;}
	g=gcd(c,b);
	c/=g; b/=g;
	cout<<c;
	if(b>1) cout<<"/"<<b;
	cout<<"\n";
	return 0;
}