Median of an Array(贪心策略,编程技巧)

本文主要是介绍Median of an Array(贪心策略,编程技巧)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给你一个由 $n$ 个整数组成的数组 $a$ 。

数组 $q_1,q_2,\dots ,q_k$ 的中位数是 $p\lceil \frac{k}{2}\rceil$ ，其中 $p$ 是按非递减顺序排列的数组 $q$ 。

例如，数组 $[9,5,1,2,6]$ 的中位数是 $5$ ，在排序数组$[1,2,5,6,9]$ 中，索引 $\lceil \frac{5}{2}\rceil =3$ 处的数字是 $5$ ；数组 $[9,2,8,3]$ 的中位数是 $3$ ，在排序数组 $[2,3,8,9]$ 中，索引 $\lceil \frac{4}{2}\rceil =2$ 处的数字是 $3$ 。

您可以选择一个整数 $i(1\le i\le n)$，并在一次操作中将 $a_i$ 增加 $1$ 。

你的任务是找出增加数组中位数所需的最少运算次数。

注意数组 $a$ 不一定包含不同的数。

输入格式

第一行包含一个整数 $n(1\le n\le 10^5)$- 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i\le 10^9)$ - 数组 $a$ 。

输出格式

输出一个整数 - 增加数组中位数所需的最少操作数。

样例输入

3
2 2 8

样例输出

1

提交链接

https://hydro.ac/d/lp728/p/12

提示

样例解释 $1$:
对第一个数字进行一次运算，得到数组 $[3,2,8]$，这个数组的中位数是 $3$，因为它是非递减排序数组 $[2,3,8]$ 中索引 $\lceil \frac{3}{2}\rceil =2$ 处的数字。原数组 $[2,2,8]$ 的中位数是 $2$，因为它是非递减排序数组 $[2,2,8]$ 中索引 $\lceil \frac{3}{2}\rceil =2$ 处的数字。因此，只需一次操作，中位数就增加了。$(3>2)$

解析

先对数组进行排序，找出数组中的中位数，即数字 $a_{\lceil \frac{n}{2}\rceil }$，让它等于 $x$ 。为了使中位数增加，即至少变为 $x+1$，数组中必须至少有 $n-\lceil \frac{n}{2}\rceil +1$ 个数字大于或等于 $x+1$。统计 $x$ 的个数即可。

count 函数：统计区间内某个数的个数。

参考代码

#include<bits/stdc++.h>
using namespace std;
int t , n;
int main()
{int n;cin >> n;vector<int> v(n);   for(int i = 0; i < n; i++)cin >> v[i];sort(v.begin() , v.end());  //排序 int id = (n + 1) / 2 - 1;  //中位数的下标(下标从0输入) int num = count(v.begin() + id , v.end() , v[id]);  //计算v[id]的个数 cout << num << endl;return 0;
}

这篇关于Median of an Array(贪心策略,编程技巧)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---