竞赛讨论区 > 只过了66.7,路过的朋友麻烦看下[已经找了好久了
头像
Q_Q_Q_Q
发布于 2020-05-02 15:52
+ 关注

只过了66.7,路过的朋友麻烦看下[已经找了好久了

#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
LL y[maxn];
LL sum[maxn];
////有重复的要取最右边的,所以是l=mid; 
LL bsearch(LL l,LL r,double x)
{
	while(l<r)
	{
		LL mid=(l+r+1)/2;
		if(y[mid]<=x) l=mid;
		else r=mid-1;
	}
	return l;
} 

int main(void)
{
	LL n,q;cin>>n>>q;
	for(LL i=1;i<=n;i++) cin>>y[i];
	sort(y+1,y+n+1);
	////sum[i]存员工位置的和 
	for(LL i=1;i<=n;i++)
		sum[i]=sum[i-1]+y[i];
	
	while(q--)
	{
		LL ans=0;
		LL a;LL b;cin>>a>>b;
		if(a>b) swap(a,b); 
		//AB中的点 
		double x=( a+b)/2;
		LL l1=bsearch(1,n,a);///l1表示小于等于A的最后下标 
		
		LL l2=bsearch(1,n,x);///l2表示小于等于x的最后下标 
		
		LL l3=bsearch(1,n,b);///l3表示小于等于B的最后下标 
//		l1--;l2--;l3--;
		////从1开始,下标即人数 
//		cout<<"x="<<x<<endl;
//		cout<<"l1="<<l1<<endl;
//		cout<<"l2="<<l2<<endl;
//		cout<<"l3="<<l3<<endl;
	
//		for(int i=1;i<=n;i++)
//		{
//			cout<<"sum["<<i<<"]="<<sum[i]<<endl;
//		}
	
		ans=a*(l1) - sum[l1] + abs( sum[l2]-sum[l1]-(l2-l1)*a )+ b*(l3-l2)-( sum[l3]-sum[l2])+ abs(sum[n]-sum[l3]-b*(n-l3) );
//		cout<<"a*(l1) - sum[l1]"<<a*(l1) - sum[l1]<<endl;
//		cout<<"abs( sum[l2]-sum[l1]-(l2-l1)*a )"<<abs( sum[l2]-sum[l1]-(l2-l1)*a )<<endl;
//		cout<<"b*(l3-l2)-( sum[l3]-sum[l2])"<<b*(l3-l2)-( sum[l3]-sum[l2])<<endl;
//		cout<<"abs(sum[n]-sum[l3]-b*(n-l3) )"<<abs(sum[n]-sum[l3]-b*(n-l3) )<<endl;
		cout<<ans<<endl;
	}
return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐