张经理的员工

题目描述

张经理的公司的办公室长达100000米，从最左端开始每间隔1米都有一个工位（从第1米开始有工位），位于第i米的工位称为i号工位，且这些工位都在一条水平线上。他有n个员工，每个员工分别位于xi号工位上（不同员工可能位于同一个工位）。

现在张经理想把员工聚集在某两个工位上，他有q套方案（每套方案包含两个工位号，两个工位号可能相同），他想知道对于每套方案，所有员工都到达两个工位中的某一个所需走的最短路径之和是多少。

输入描述：

第一行输入两个正整数n, q

第二行输入n个正整数xi，分别代表第i个员工的工位

之后q行每行输入两个整数a，b，代表该套方案要求的两个集合位置

（1<=n,q,xi,a,b<=10^5)

输出描述：

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

示例输入：

3 2
1 3 5
1 4
2 1

示例输出：

2
4

算法思想：

参考资料

张经理的员工——前缀和处理&&二分思想

张经理的员工---------------------------思维(前缀和)

扩展资料

前缀和

[Algorithm]前缀和

算法1：最快最简单的排序——桶排序

漫画：什么是计数排序？

参考代码：

#include<iostream>
#define LEN 100001

using namespace std;

int site[LEN];//当前工位号下的员工数 
int sum1[LEN];//工位号的前缀和
int sum2[LEN];//员工数的前缀和

int main(){

    int n,q;//n个员工,q套方案
    cin >> n >> q;

    /*记数排序方式输入*/
    for(int i=0;i<n;i++){ 
        int temp;
        cin >> temp;
        site[temp]++;//工位号"temp"下的员工数+1 
    }

    /*前缀和处理*/ 
    for(int i=1;i<=LEN;i++){
        sum1[i]=sum1[i-1]+site[i]*i; 
        sum2[i]=sum2[i-1]+site[i];
    }

    while(q--){

        int a,b;//代表该套方案要求的两个集合位置
        cin >> a >> b; 

        if(a>b)
            swap(a,b);//保证a<=b 

        int mid=(a+b)/2;//二分法

        int path=0;//路径长度初始化 

        /*1~a*/ 
        path+=sum2[a]*a-sum1[a];
        /*a~mid*/
        path+=(sum1[mid]-sum1[a])-(sum2[mid]-sum2[a])*a;
        /*mid~b*/
        path+=(sum2[b]-sum2[mid])*b-(sum1[b]-sum1[mid]);
        /*b~LEN*/
        path+=(sum1[LEN]-sum1[b])-(sum2[LEN]-sum2[b])*b;

        cout << path << endl;
    }

    return 0;
}