7-4 中位数
admin
2024-01-29 01:12:50
0次
| 一个有 n 个整数的数组 a，n是一个奇数。 每次可以选择数组里的一个元素 ai 并把这个元素加上 1。 在至多 k 次操作之后，数组的中位数最大能变成多少。 输入格式:多组输入 第一行两个整数 n,k(1≤n≤2×105,1≤k≤109)。 第二行 n 和整数 a1,a2,......,an。 输出格式:k 次操作后数组的中位数。 |
输入样例:
3 2
1 3 5
输出样例:
5简单讲解
首先将数据读入nums[]，排序后求得当前中位数的下标mid
因为一共可以加K，要求让nums[mid]最大
所有答案就是 "nums[mid]+k" ？？？ 显然是不对的!
因为当nums[mid] == nums[mid+1] 时候， 前者再加1，中位数就变了...
而我们要做的，就是一直填中位数的位置，只看位置不看数
所以我们要用一个数(文中为num)，动态的记录:
nums[mid] == nums[mid+1] == .... == nums[mid+num] 的位置
核心思想
只要让判断
nums[mid]+z == nums[mid+1]+z==...==nums[mid+num]+z == nums[mid+num+1]
且 k >= z*num ,我们就可把mid位置的高度同步到nums[mid+num+1]的高度
即此时 k-=z*num，num++;
当 k < z*num时，那么nums[mid]最终的值就是 当前nums[mid]+=k/num
C/C++
#include
long long nums[100001];
int n,k;
void OP();
int main()
{while (scanf("%d %d",&n,&k)!=EOF) OP();return 0;
}
void OP()
{for(int z=0;z1){flag /= 2;for(int z=0;z=0){if(key=(nums[mid+num]-nums[mid])*num){k -= (nums[mid+num]-nums[mid])*num;nums[mid] = nums[mid+num];num++;}printf("%lld\n",nums[mid]+k/num);
} 相关内容
热门资讯
宁波一游乐园内装饰树起火，工作...
7月6日，多位网友在社交平台发视频称，浙江宁波罗蒙环球乐园一棵圣诞树突然起火。 现场视频显示，一处游...
快乐不放假 公园玩一夏 全市4...
深圳新闻网2025年7月7日讯（深圳商报记者 文灿）7月5日，深圳公园“快乐不放假，公园玩一夏”夏日...
为了帮女儿照顾孩子，我和儿媳妇...
为了帮女儿照顾孩子，我和儿媳妇闹翻了01 “带着你的外孙走。” 一声尖锐的叫喊声过后，传来门被重...
孩子课上听不懂老师讲的怎么办？
孩子课上听不懂老师讲的怎么办？到外面培训机构培训一下，比如新东方教育之类的孩子刚上一年级，课上听不懂...
安徽一爸爸火车上睡着，儿子走丢...
安徽一爸爸火车上睡着，儿子走丢了都不知道，爸爸带娃到底有多靠谱？实在是太不靠谱了，这样的行为实在是太...
大家支持小学生向老师举报、告状...
大家支持小学生向老师举报、告状、告密吗？我个人不支持这样的做法，这样有个弊端，可能把孩子引向一个背后...
麻烦各位推荐几本好看的穿越小说
麻烦各位推荐几本好看的穿越小说绾青丝 独步天下 醉玲珑 丑颜倾城芊泽花，醉玲珑，跨过千年来爱你，暴...
星际战甲怎么一键分解所有重复m...
星际战甲怎么一键分解所有重复mod对着mod，按鼠标中键，即可全选该mod。按重复数量排序，即可方便...
电视剧《五星大饭店》有续集吗？...
电视剧《五星大饭店》有续集吗？是什么结局啊？没有续集。话说没有拍续集的打算。一般现在看的续集都是网友...
高中会考没过就一定没高中毕业证...
高中会考没过就一定没高中毕业证吗？高中会考没过就一定没高中毕业证吗不一定那，没过也可以领的当然不是，...
为什么我的仙剑奇侠传四玩道慕容...
为什么我的仙剑奇侠传四玩道慕容紫英那就卡掉，不能继续啊？我仙四一到紫英那放动画那就卡住，然后关闭了啊...
YES！光之美少女5GOGO有...
YES！光之美少女5GOGO有哪些剧场版有YES，光之美少女剧场版1、光之美少女剧场版2、光之美少女...
住家保姆的服务内容有哪些
住家保姆的服务内容有哪些这个要跟保姆自己谈了要看你给的价格了
钓鱼坠子的制作方法有什么？
钓鱼坠子的制作方法有什么？进行海竿抛钩时，由于水底不平或水草、树根过多，挂钩失坠时有发生。因此在垂钓...
问下，图里的那个动漫人物是出自...
问下，图里的那个动漫人物是出自哪个动漫薄樱鬼斋藤一出自动漫《薄樱鬼》人物名为：斋藤一这是原图我觉得像...
死神黑崎一护是不是灭却师？第二...
死神黑崎一护是不是灭却师？第二部什么时候出？一护妈妈是灭却师，爸爸是死神，所以算个混血儿→ →也就是...
点到为止的意思
点到为止的意思点到为止：说话时只是轻轻触及话题的边缘,而不必深入谈论,但是已经让对方明了意图即可到了...
《余生请多指教》热播，顾医生身...
《余生请多指教》热播，顾医生身上有哪些特质？特别温柔，特别专一，会安慰人，会讲大道理，特别暖心。顾医...
浩态狂香昔未逢，红灯烁烁绿盘龙...
浩态狂香昔未逢，红灯烁烁绿盘龙，觉来独对情惊恐，身在仙宫第九重。韩愈的哪一首诗。名字啊什麼？顺便求诗...