暴力枚举，巧思处理。

好久没写题，今天来一道绿的练手。实际上这个题感觉跟2023NOIP-T1一样，没什么思维，纯粹考察一个问题转化。

题目链接

题目描述

Q村非常非常Qiong，整个村只有一条路。在这条路上，有 N 户人家，因为条件有限，所以一个点上可能有多户人家。因为山区运输条件落后，所以扶贫队只能修筑k个信号站，并且他们希望各电站的不合理值之和最小。信号站的不合理值是指该信号站到每户人家的距离之和。

扶贫队善于修筑电站，但是他们不擅长选址（因为数学不好QwQ），他们希望你>>编程高手，来帮助他们选择修筑信号站的最佳地点，使得k个信号站的不合理值最小。

距离求解方法:若某信号站的坐标为 x ,某户人家的坐标为 y ,那么该信号站与该人家的距离为 |x-y| （即取绝对值）。

数据保证人家数大于信号站数。放置信号站的位置坐标必须为整数。一个位置上只能放一个信号站。

输入格式

共2行，

第一行，读入 n，k，分别代表人家数和信号站数；

第二行，读入各户人家的坐标 a_i（保证为整数），用空格隔开。

输出格式

仅一行，输出最小的不合理值之和。

样例 #1

样例输入 #1

7 2
1 1 2 2 3 3 4

样例输出 #1

13

提示

样例解释

在2和3的位置上放置信号站（方案不唯一）。

数据范围

对于 70\% 的数据，n,k\leq 10^3；
对于 100\% 的数据，n \leq 1000000, 0 \leq a_i \leq 10 ^ 6。

O(n) 思路

首先想明白，所有信号点必然连续。因为它是一个凹函数。

首先预处理所有点到坐标为0点的贡献，然后依次往后枚举每个可能的点。移动过程可以抽象为离左边的所有点都远去1，离右边的所有点都变近1，所以可以用前缀和预处理一下。详见注释。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int M = 1e6;
const int N = 2e6 + 10;
ll cnt, np[N], ans[N], ret, ret0;
int n, m, maxn;

int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d%d", &n, &m);
  int tmp;
  for(int i = 1; i <= n; i++) {
    scanf("%d", &tmp);
    tmp += M;
    np[tmp] += 1;
    cnt += tmp;
    maxn = maxd(maxn, tmp);
  }
  ans[0] = cnt, np[0] = 0;
  // printf("%lld ", cnt);
  for(int i = 1; i <= maxn; i++) {
    np[i] += np[i - 1];
    //前缀和记录前面有多少个，每当往后走去掉前面的加上后面的
    cnt += np[i - 1];//把左边的加上
    cnt -= n - np[i - 1];//把右边的去掉
    ans[i] = cnt;
    // printf("%lld", ans[i]);
  }
  for(int i = 1; i <= m; i++) {
    ret += ans[i];
  }
  ret0 = ret;
  for(int i = m + 1; i <= maxn; i++) {
    ret += ans[i] - ans[i - m];
    ret0 = mind(ret0, ret);
  }
  printf("%lld\n", ret0);
  return 0;
}

O(nlogn) 思路

请查看 dalao的题解