#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) 回帖