只过了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;
}

全部评论
upper__bound()不香嘛
点赞 回复 分享
发布于 2020-05-03 09:33
你应该和我一样,二分搜索没有处理边界值
点赞 回复 分享
发布于 2020-05-02 21:31

相关推荐

04-17 10:16
门头沟学院 Java
小浪_coder:24届很难找了,马上25的都毕业了还有很多没找到的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务