A 张经理的员工

题目链接

来源：牛客网

题目描述

张经理的公司的办公室长达100000米，从最左端开始每间隔1米都有一个工位（从第1米开始有工位），位于第i米的工位称为i号工位，且这些工位都在一条水平线上。他有n个员工，每个员工分别位于xi号工位上（不同员工可能位于同一个工位）。 现在张经理想把员工聚集在某两个工位上，他有q套方案（每套方案包含两个工位号，两个工位号可能相同），他想知道对于每套方案，所有员工都到达两个工位中的某一个所需走的最短路径之和是多少。

输入描述:
第一行输入两个正整数n, q第二行输入n个正整数xi，分别代表第i个员工的工位之后q行每行输入两个整数a，b，代表该套方案要求的两个集合位置（1<=n,q,xi,a,b<=105)

输出描述:
对于每套方案，输出一个整数代表答案，每个答案独占一行。

示例1

输入

3 2
1 3 5
1 4
2 1

输出

2
4

这题直到比赛结束都没能写出来，一直超时，试了各种剪枝也不行，后面看到别人的代码才恍然大悟，得构造一个好的计算方法，才能更快的计算此题。对于每次操作，假设更小的数字是a，更大的是b，然后对于所有的点进行分类，大体分为三类，第一类是a左边的点，第二类是a，b之间的点，第三类是b右边的点。

如何求：只要知道一类点的求法，其他的几种情况都是一样的道理。这里先求a左边的点，那么我们首先可以知道，对于每个a左边的点，要通过的距离就是a-xi（此题的关键），那么这里假设一个数组preL[i]代表i位置前（包含i）员工个数总和，preLsum[i]代表i位置前员工下标总和。那么对于a前面的所有点的答案就是：a*preL[a]-preLsum[a]，也就是对于每个（a-xi）的加和的结果。只要理解了这种情况，其他的都是用相同的思路去求，只是在a,b之间的需要再次分为a+1~（a+b）/2和(a+b)/2+1 ~(b-1)两个小情况。

更具体的细节在代码里面或许更好说清楚：

代码说明：staff[i]为按输入顺序存储的员工所在位置的数组，num[i]代表位置为i的员工个数，preL[i]代表i位置前（包含i）员工个数总和，preLsum[i]代表i位置前（包含i）员工下标总和，preR[i]代表i位置后（包含i）员工个数总和，preRsum[i]代表i位置后（包含i）员工下标总和。

#include<bits/stdc++.h>
using namespace std;
long long staff[100010],num[100010],sum1,sum2,preL[100010],preLsum[100010],preR[100010],preRsum[100010];
int main()
{int n,q;scanf("%d%d",&n,&q);for(int i=1;i<=n;++i){scanf("%lld",&staff[i]);num[staff[i]]++;//储存下标为i的员工的个数}sum1=sum2=0;for(int i=1;i<=100000;++i){if(num[i]){sum1+=num[i];sum2+=i*num[i];}preL[i]=sum1;//计算i位置左侧所有员工个数preLsum[i]=sum2;//计算i位置左侧所有员工下标总和}sum1=sum2=0;for(int i=100000;i>0;--i){if(num[i]){sum1+=num[i];sum2+=i*num[i];}preR[i]=sum1;//计算i位置右侧员工个数preRsum[i]=sum2;//计算i位置右侧员工下标总和}for(int i=0;i<q;++i){int a,b;scanf("%d%d",&a,&b);if(a>b)swap(a,b);long long x1,x2,x3,x4;x1=a*preL[a]-preLsum[a];//a左边的最小距离和x2=preRsum[b]-b*preR[b];//b右边的最小距离和x3=(preLsum[(a+b)/2]-preLsum[a])-(a*(preL[(a+b)/2]-preL[a]));//a,b中间偏向a的最小距离和x4=(b*(preL[b]-preL[(a+b)/2]))-(preLsum[b]-preLsum[(a+b)/2]);//a,b中间偏向b的最小距离和printf("%lld\n",x1+x2+x3+x4);}
}