中位数

引入：曼哈顿距离
在一维空间下，曼哈顿距离定义如下： $d(x,y)=|x-y|$
在二维空间下，曼哈顿距离定义如下： $d(x,y)=|x_1-y_1|+|x_2-y_2|$

货仓选址

题意：在一条数轴上有 $n$ 家商店，它们的坐标分别为 $a_1 ... a_n$ ，求一个到每家商店的距离之和最小的值。

首先，最直接的思路就是枚举 $[min(a_1...a_n), max(a_1...a_n)]$ 的每个点，求一遍距离，复杂度为 $O(n^2)$
其实可以知道最优的方案，那就是取中位数，每一个点到中位数的距离，都是满足全局的最优性，而不是局部最优性。
先给出结论：取所有坐标中位数，如果n是奇数，那么中位数唯一；如果n是偶数，可以选中间两个数之间的任何一个位置
比如： $1, 3, 4, 9, 18$ 明显建在 $4$ 处最优。
比如： $1,2,6,9$ 可以看出建在 $2,6$ 处都可以，因为距离一样，可以通过画图求证出。那要是建在 $3$ 呢？其实距离也是最佳的，只不过 $2,6$ 更清晰。
所以此题就是求中位数

/*
 * @Description: 
 * @Author: NEFU AB_IN
 * @version: 1.0
 * @Date: 2021-02-16 17:07:15
 * @LastEditors: NEFU AB_IN
 * @LastEditTime: 2021-03-03 23:11:30
 */
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define MP                          make_pair
#define PB                          emplace_back
#define SZ(X)                       ((int)(X).size())   
#define mset(s, _)                  memset(s, _, sizeof(s))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
#define forn(i, l, r)                for (int i = l; i <= r; i++)
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
const int INF = 0x3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    int a[n + 10], ans = 0;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int mid = (1 + n) >> 1;
    for(int i = 1; i <= n; i ++) ans += abs(a[i] - a[mid]);
    cout << ans << endl;
}

int main()
{
    IOS;
    solve();
    return 0;
}

其实再往深处想，既然要是求距离，而不是求点，那么我们不妨假设存在这么一个点 $x$ ，那么我们很容易就看出：**根据 $x$ 对称的两个点的距离，就是两个点分别到 $x$ 距离的和。**

所以此题为求两端差的和。

/*
* @Description: 
* @Author: NEFU AB_IN
* @version: 1.0
* @Date: 2021-02-16 17:07:15
* @LastEditors: NEFU AB_IN
* @LastEditTime: 2021-03-03 23:25:19
*/
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define MP                          make_pair
#define PB                          emplace_back
#define SZ(X)                       ((int)(X).size())   
#define mset(s, _)                  memset(s, _, sizeof(s))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
#define forn(i, l, r)                for (int i = l; i <= r; i++)
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
const int INF = 0x3f3f3f3f;

void solve(){
int n;
cin >> n;
int a[n + 10], ans = 0;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n / 2; i ++) ans += a[n - i + 1] - a[i];
cout << ans << endl;
}

int main()
{
IOS;
solve();
return 0;
}

# [<font color=#6495ED size=6>街区最短路径问题</font>](https://nanti.jisuanke.com/t/T1549)
题意：在二维坐标下，要建一个邮局，使得各个住户到邮局的距离之和最少，求最短距离。

*  由于这里求的时**曼哈顿距离**，那么我们就可以将二维降为一维考虑。问题就转变为了两个**货仓选址**问题。
* 两种思路都可以做。

```cpp
/*
 * @Description: 
 * @Author: NEFU AB_IN
 * @version: 1.0
 * @Date: 2021-02-16 17:07:15
 * @LastEditors: NEFU AB_IN
 * @LastEditTime: 2021-03-03 23:25:19
 */
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define MP                          make_pair
#define PB                          emplace_back
#define SZ(X)                       ((int)(X).size())   
#define mset(s, _)                  memset(s, _, sizeof(s))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
#define forn(i, l, r)                for (int i = l; i <= r; i++)
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
const int INF = 0x3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    int a[n + 10], b[n + 10], ans = 0;
    for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n / 2; i ++) ans += a[n - i + 1] - a[i] + b[n - i + 1] - b[i];
    /*
    int mid = (1 + n) >> 1;
    for(int i = 1; i <= n; i ++) ans += abs(a[i] - a[mid]) + abs(b[i] - b[mid]);
    */
    cout << ans << endl;
}

int main()
{
    IOS;
    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

Codeforces Round #703 (Div. 2)

B Eastern Exhibition

题意：在二维坐标下，要建一个博物馆，使得各个住户到博物馆的距离之和最短，求有多少个这种位置。

这其实还是货仓选址问题，只不过不是求距离，而是求有多少个这种点。结论说的很清楚了：奇数只有一个；偶数有两个，而且中间的点也可以。最后乘法原理即可

/*
 * @Description: 
 * @Author: NEFU AB_IN
 * @version: 1.0
 * @Date: 2021-01-25 23:11:38
 * @LastEditors: NEFU AB_IN
 * @LastEditTime: 2021-02-18 23:41:00
 */
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define MP                          make_pair
#define PB                          emplace_back
#define SZ(X)                       ((int)(X).size())   
#define mset(s, _)                  memset(s, _, sizeof(s))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
#define forn(i, l, r)                for (int i = l; i <= r; i++)
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
const int INF = 0x3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    ll x[n + 10], y[n + 10];
    for(int i = 1; i <= n ; i ++) cin >> x[i], cin >> y[i];
    sort(x + 1, x + 1 + n);
    sort(y + 1, y + 1 + n);
    if(n & 1){
        cout << 1 << endl;
    } 
    else{
        ll x1 = x[n / 2], x2 = x[n / 2 + 1];
        ll y1 = y[n / 2], y2 = y[n / 2 + 1];
        cout << (1ll) * (x2 - x1 + 1) * (y2 - y1 + 1) << endl;
    }
}

int main()
{
    IOS;
    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

D Max Median

题意：给定一个长度为 $n$ 的数组 $a$ 。找到长度至少为 $k$ 且中位数最大的子数组 $a [l..r]$ ，输出最大的中位数。

知识点：二分 + 前缀和 + 贪心

思路：直接枚举所有可能的答案，并且检查答案是否合法，枚举的同时采用二分优化。二分具有单调性，如果中位数至少是 $x$ ，那么比 $x$ 小的数也可以，采用二分向右搜索。
那么问题就转变为了：**是否存在一个长度至少是 $k$ 的连续子段，满足中位数至少为 $x$ ？**
继续转变为：**是否存在一个长度至少是 $k$ 的连续子段，满足 $≥x$ 的数的个数严格大于 $<x$ 的数的个数？**
下面就用到比较神奇的前缀和来解决，构造一个数组 $s[i]=(a[i]>=x?1:−1)$ ，做一个前缀和，如果有一段长度至少为 $k$ 的连续子段严格大于0，那么说明 $>=x$ 的数更多，说明可以继续向右搜索。
在实现前缀和的同时，可以用贪心来优化，找一个 $i≥k$ 以及一个 $j∈[0,i−k]$ .满足 $s[j]−s[i]>0$ .那么贪心 $s[j]$ 只用前面的最小值,维护前缀最小值就可以判断了。

/*
 * @Description: 
 * @Author: NEFU AB_IN
 * @version: 1.0
 * @Date: 2021-02-16 17:00:46
 * @LastEditors: NEFU AB_IN
 * @LastEditTime: 2021-03-02 22:04:45
 */
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define MP                          make_pair
#define PB                          emplace_back
#define SZ(X)                       ((int)(X).size())   
#define mset(s, _)                  memset(s, _, sizeof(s))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
#define ls                          i << 1
#define rs                          i << 1 | 1
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
const int INF = 0x3f3f3f3f;

const int N = 2e5 + 7;
int a[N], s[N], n, k, m[N];

bool check(int x){
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + (a[i] >= x ? 1 : -1);
    for(int i = 1; i <= n; i ++) m[i] = min(m[i - 1], s[i]);
    for(int i = k; i <= n; i ++) {
        if(s[i] - m[i - k] > 0) return true;
    }
    return false;
}

int main()
{
    IOS;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    } 
    int l = 1, r = n;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

完结。