石家庄公司网站建设,专业做网文的网站有哪些,宁波seo排名优化,十大难进的互联网公司最大中位数 给定一个由 n 个整数组成的数组 a#xff0c;其中 n 为奇数。
你可以对其进行以下操作#xff1a;
选择数组中的一个元素#xff08;例如 ai#xff09;#xff0c;将其增加 1#xff08;即#xff0c;将其替换为 ai1#xff09;。 你最多可以进行 k 次操…最大中位数 给定一个由 n 个整数组成的数组 a其中 n 为奇数。
你可以对其进行以下操作
选择数组中的一个元素例如 ai将其增加 1即将其替换为 ai1。 你最多可以进行 k 次操作并希望该数组的中位数能够尽可能大。
奇数长度的数组的中位数是数组以非降序排序后的中间元素。
例如数组 [1,5,2,3,5] 的中位数为 3。
输入格式 第一行包含两个整数 n 和 k。
第二行包含 n 个整数 a1,a2,…,an。
输出格式。 输出一个整数表示通过操作可能得到的最大中位数。
数据范围 对于 30% 的数据1≤n≤5。 对于 100% 的数据1≤n≤2×1051≤k≤1091≤ai≤109。
输入样例1 3 2 1 3 5 输出样例1 5 输入样例2 5 5 1 2 1 1 1 输出样例2 3 输入样例3 7 7 4 1 2 4 3 4 4 输出样例3 5
#include iostream
#include algorithm
using namespace std;
int main()
{int n, k;int ch[200010];cin n k;if (n1) //特判因为我下面写的不是很好没有囊括这个{cinch[0];ch[0]k;coutch[0];return 0;}for (int i 0; i n; i){cin ch[i];}sort(ch, ch n);int cou n / 2;int i;for (i cou; i n; i){if ((i - cou) * (ch[i] - ch[i - 1]) k)break;else{k - (i - cou) * (ch[i] - ch[i - 1]);ch[i - 1] ch[i];}}i--;if (k 0){if ((i - cou) * (ch[i] - ch[i - 1]) k)//break的一种情况没到底{while ((i - cou) k){k - (i - cou);ch[i - 1];}coutch[i-2];}else//第二种中位数后面都一样了{while ((i - cou 1) k){k - (i - cou1);ch[i];}coutch[i];}}else {coutch[i-1];}
}
