首页 > 中位数
头像
AB-IN
发布于 2021-03-12 22:10
+ 关注

中位数

Powered by:NEFU AB_IN

引入： 曼哈顿距离
在一维空间下，曼哈顿距离定义如下：
在二维空间下，曼哈顿距离定义如下：

货仓选址

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

  • 首先，最直接的思路就是枚举的每个点，求一遍距离，复杂度为
  • 其实可以知道最优的方案，那就是取中位数，每一个点到中位数的距离，都是满足全局的最优性，而不是局部最优性。
  • 先给出结论：取所有坐标中位数，如果n是奇数，那么中位数唯一；如果n是偶数，可以选中间两个数之间的任何一个位置
  • 比如： 明显建在处最优。
  • 比如： 可以看出建在处都可以，因为距离一样，可以通过画图求证出。那要是建在呢？其实距离也是最佳的，只不过更清晰。
  • 所以此题就是求中位数 
/*
 * @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;
}
  • 其实再往深处想，既然要是求距离，而不是求点，那么我们不妨假设存在这么一个点，那么我们很容易就看出：**根据对称的两个点的距离，就是两个点分别到距离的和。**
  • 所以此题为求两端差的和。
    /*
* @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

题意：给定一个长度为的数组。 找到长度至少为且中位数最大的子数组，输出最大的中位数。

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

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

完结。

2025最新求职资料大礼包领取
真题
历年笔试真题附答案
博世23年秋招软件工程师
吉比特校招技术岗笔试
ThoughtWorks2018校招面试题
全部 >
面经
面试常考问题整理
管理类双非硕的23秋招记录＆反思
22届-国企上岸经验分享
2022考研失败春招选手的群面攻略（适用于菜鸡互啄型）
全部 >
内推
员工内推码获取
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(1) 回帖
加载中...
话题 回帖
博文推荐

相关热帖

近期热帖

近期精华帖

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”