暴力枚举，巧思处理。
好久没写题，今天来一道绿的练手。实际上这个题感觉跟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的题解
正文完
