/ 注册

去牛客

竞赛讨论区 > 尝试证明了一下C

sishenzhimu

发布于 05-14 00:10

+ 关注

尝试证明了一下C

先讨论个数为偶数，不妨设排序后数组为 $a_1,...,a_{2n}$ ，讨论序列 $a_1a_{2n},...,a_{n}a_{n+1}$ 。对任意 $p,q$ 满足 $p\lt q$ 且 $p+q\ne 2n+1$ ，有 $a_p\le a_q,a_{2n+1-p} \ge a_{2n+1-q}$

如果 $a_pa_{2n+1-p}$ 与 $a_qa_{2n+1-q}$ 不是序列的最值，交换 $a_p,a_q$ 会使最大值变大/不变和（或）最小值变小/不变
如果 $a_pa_{2n+1-p}$ 是序列的最大值 $\max$ ，交换 $a_p,a_q$ 得到的 $a_qa_{2n+1-p} \ge a_pa_{2n+1-p} = \max$
如果 $a_qa_{2n+1-q}$ 是序列的最大值 $\max$ ，交换 $a_p,a_q$ 得到的 $a_qa_{2n+1-p} \ge a_qa_{2n+1-q} = \max$
如果 $a_pa_{2n+1-p}$ 是序列的最小值 $\min$ ，交换 $a_p,a_q$ 得到的 $a_pa_{2n+1-q} \le a_pa_{2n+1-p} = \min$
如果 $a_qa_{2n+1-q}$ 是序列的最小值 $\min$ ，交换 $a_p,a_q$ 得到的 $a_pa_{2n+1-q} \le a_qa_{2n+1-q} = \min$

再讨论个数为奇数，不妨设排序后数组为 $a_1,...,a_{2n+1}$ ，讨论序列 $a_1a_{2n},...,a_{n}a_{n+1},a_{2n+1}$ 。对任意 $p$ 满足 $p \lt 2n+1$ 有 $a_p \le a_{2n+1}$ 。

如果 $a_pa_{2n+1-p}$ 与 $a_{2n+1}$ 不是序列的最值，交换 $a_p,a_{2n+1}$ 会使最大值变大/不变和（或）最小值变小/不变
如果 $a_{2n+1} = \max$ ，交换 $a_p,a_{2n+1}$ 得到的 $a_{2n+1-p}a_{2n+1} \gt a_{2n+1} = \max$
如果 $a_{p}a_{2n+1-p} = \max$ ，交换 $a_p,a_{2n+1}$ 得到的 $a_{2n+1-p}a_{2n+1} \gt a_{p}a_{2n+1-p} = \max$
如果 $a_{2n+1} = \min$ ，交换 $a_p,a_{2n+1}$ 得到的 $a_{p} \le a_{2n+1} = \min$
如果 $a_{p}a_{2n+1-p} = \min$ ，交换 $a_p,a_{2n+1}$ 得到的 $a_{p} \lt a_{p}a_{2n+1-p} = \min$

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

全部评论

(0) 回帖

加载中...

话题同步到我的动态回帖

返回全部帖子

本文相关内容

等你来战

查看全部

牛客周赛 Round 48

报名截止时间：2024-06-23 21:00
牛客小白月赛97

报名截止时间：2024-06-28 21:00
北京建筑大学2024年程序设计竞赛（同步赛）

报名截止时间：2024-06-30 18:00
牛客练习赛127

报名截止时间：2024-07-05 21:30
2024牛客暑期多校训练营1

报名截止时间：2024-07-16 17:00
2024牛客暑期多校训练营2

报名截止时间：2024-07-18 17:00

热门推荐

扫描二维码，关注牛客
意见反馈
下载牛客APP，随时随地刷题

牛客竞赛，专业的竞技算法训练平台: 扫描二维码，进入QQ群



扫码关注“比赛自动姬”

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved admin@nowcoder.com
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号