题解 P4998 【信号站】

lamboo · 2018-11-03 20:42:36 · 题解

显然，对于每个点x，它的不合理值为y=\sum_{i=1}^n\mid x-a_i \mid。显然（根据绝对值的几何意义），这个函数有且仅有一个最小值。且在最小值左右两边的函数图像分别为单调递减、单调递增。大概是这么一个图像。

我们在这道题中要找k个整点，使其对应的y值之和最小。我们可以先求出最小值。显然（根据绝对值的几何意义），在a数组有序的前提下\sum_{i=1}^n\mid x-a_i \mid_{min}=\sum_{i=1}^n\mid a_{\lfloor \frac{n}{2} \rfloor }-a_i \mid。我们发现只有 a_{\lfloor \frac{n}{2} \rfloor} 会对最小值产生影响，而其它数的顺序对答案没有影响。所以，我们可以计数排序，也可以通过快速排序舍去区间加快速度（虽然良心出题人并没有卡普通nlogn的排序）。然后，我们可以利用函数的单调性，往两边扩展计算，取最小值，让小的点继续去扩展，将答案累加。

注意:

1. 信号站建在负数位置的情况。

2. 要开long long

具体详见代码

#include<cstdio>
using namespace std;
#define N 2000001
long long a[N],b[N];
long long n;
void sort(long long l,long long r)
{
    int i,j,x,y;
    if (l>n/2) return;  
    if (r<n/2) return;  //舍去不必要的区间
    i=l;j=r;
    x=a[l+r>>1];
    do
    {
        while (a[i]<x) ++i;
        while (x<a[j]) --j;
        if (i<=j)
        {
            y=a[i];
            a[i]=a[j];
            a[j]=y;
            ++i;--j;
        }
    }
    while (i<=j);
    if (l<j) sort(l,j);
    if (i<r) sort(i,r);
}
inline long long abs(long long x)
{
    if (x>0) return x;
    return -x;
}
int main()
{
    int k;
    scanf("%lld %d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]),b[a[i]]++;  //b[x]表示第x个位置有几户人家
    sort(1,n);
    long long ans=0;
    long long x=a[(n+1)/2],y=x+1;
    long long x_ans=0,y_ans=0,x_num=0,y_num=0;
    for (int i=1;i<=n;i++) 
        if (a[i]>x) ++x_num;  //保存在x右边的数的个数
    for (int i=1;i<=n;i++)  
        if (a[i]<y) ++y_num;  //保存在y左边的数的个数
    for (int i=1;i<=n;i++) x_ans+=abs(x-a[i]);
    for (int i=1;i<=n;i++) y_ans+=abs(y-a[i]);
    for (int i=1;i<=k;i++)
    {
        if (x_ans<=y_ans)  //取小的点扩展，累加答案
        {
            ans+=x_ans;
            x_ans+=x_num+b[x]-(n-x_num-b[x]);  //计算下一个点对答案的贡献。
            if (b[x]) x_num+=b[x];  //更新在x右边的数的个数
            --x;
        }
        else
        {
            ans+=y_ans;
            y_ans+=y_num+b[y]-(n-y_num-b[y]);
            if (b[y]) y_num+=b[y];
            ++y;
        }
    }
    printf("%lld\n",ans);
    return 0;
}