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

张经理的员工

https://ac.nowcoder.com/acm/contest/5403/A

链接：https://ac.nowcoder.com/acm/contest/5403/A
来源：牛客网

题目描述

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

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

中心思想

桶排序，前缀和处理，二分法

题目思路

【桶排序输入】
在题目中采用桶排序方式对工号进行输入。

 //n为员工个数
//site[i]记录工位为i号的员工个数
for(int i=0;i<n;i++)
{
    int temp;
    scanf("%d",&temp);
    site[temp]++;
}

【前缀和处理】
设置两个前缀和数组sum1和sum2。
其中，sum1[i]存放工位小于i的员工的工位号和；sum2[i]存放工位号小于i的员工数量。

    for(int i=2;i<=MAXN+1;i++)
    {
        sum1[i]=sum1[i-1]+site[i-1]*(i-1);
        sum2[i]=sum2[i-1]+site[i-1];
    }

【二分思想】
取所选工位号的中间值mid=(a+b)/2，其中，工位号小于等于mid的向a移动，大于mid的向b移动。
选中1号（a）和4号（b）作为目标工位，则mid为2。
以下图为例：
图片说明

所有员工被分为两大部分：向a移动的部分和向b移动的部分。
对于向a移动的部分，分为a左边员工的移动和a右边员工的移动：
a左边：ans = sum2[a] * ( a - sum1[a]/sum2[a] ) = sum2[a] * a - sum1[a]
a右边：ans = ( sum2[mid+1] - sum2[a+1] ) * (( sum1[mid+1] - sum1[a+1] )/( sum2[mid+1] - sum2[a+1] ) - a ) = ( sum1[mid+1] - sum1[a+1] ) - ( sum2[mid+1] - sum2[a+1] ) * a
对于向b移动的部分同理可得，不再赘述。

//a左边（1~a）    
ans+=a*sum2[a]-sum1[a];
//a右边（a~mid）
ans+=(sum1[mid+1]-sum1[a+1])-(sum2[mid+1]-sum2[a+1])*a;
//b左边（mid+1~b）
ans+=(sum2[b]-sum2[mid+1])*b-(sum1[b]-sum1[mid+1]);
//b右边（b~MAX）
ans+=sum1[MAXN+1]-sum1[b+1]-(sum2[MAXN+1]-sum2[b+1])*b;

完整代码如下：

#include<stdio.h>
#define MAXN 100000

int site[MAXN+1]={0};//工位号与当前下标相同的员工数 
int sum1[MAXN+1]={0};//小于当前下标的工位号之和 
int sum2[MAXN+1]={0};//工位号小于当前下标的人数

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    //桶排序方式输入 
    for(int i=0;i<n;i++)
    {
        int temp;
        scanf("%d",&temp);
        site[temp]++;
    }
    //前缀和处理 
    for(int i=2;i<=MAXN+1;i++)
    {
        sum1[i]=sum1[i-1]+site[i-1]*(i-1);
        sum2[i]=sum2[i-1]+site[i-1];
    }

    for(int i=1;i<=q;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        //二分法，所选工位的中间值 
        int mid=(a+b)/2;
        int ans=0;
        //保证a<=b 
        if(a>b)
        {
            int t=a;
            a=b;
            b=t;
        }
        //a左边（1~a）
        ans+=a*sum2[a]-sum1[a];
        //a右边（a~mid）
        ans+=(sum1[mid+1]-sum1[a+1])-(sum2[mid+1]-sum2[a+1])*a;
        //b左边（mid+1~b）
        ans+=(sum2[b]-sum2[mid+1])*b-(sum1[b]-sum1[mid+1]);
        //b右边（b~MAX）
        ans+=sum1[MAXN+1]-sum1[b+1]-(sum2[MAXN+1]-sum2[b+1])*b;
        printf("%d\n",ans);
    }
    return 0;
 }

算法复杂度为O(q)。