Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom6月前

04/20
16:46
二分法 贪心

[czyz 2017.04.20 NOIP 模拟赛]

A:http://czyzuoj.com/problem/83

B:http://czyzuoj.com/problem/84

C:http://czyzuoj.com/problem/85

基础排序算法练习赛(雾)

A:先把所有课程按照已经修完的学分从大到小排序,然后0~n枚举把多少课程学分修完,二分算出剩下的天数最多能把没学完的所有课学到多少,复杂度O(nlogn)

 

B:先把所有数排序。我们发现A和B都取了n/2-1个数,然后可以推出答案一定是 min(a[i+n / 2] - a[i])

先证明答案最小是这个数,因为a[i + n / 2]和a[i]之间刚好相隔了n/2-1个数,所以B不可能把中间的所有数和a[i]或者a[i + n/2]同时取走。

然后证明答案最大是这个数,我们把所有 i和i + n / 2 配对,差最小的是x1, x2。如果A选的不是x1,x2,那么B就选和A选的配对的。假如A选的是x1,那么随便从x1+1到x2-1中找一个没有配对的x3(很显然从x1+1到x2-1包括了除了x1,x2以外的所有配对),B选和x3配对的并把x2,x3配对,x2-x3肯定小于x2-x1,所以就可以保证所有配对中永远存在一个配对使得他们的差小于等于x2-x1。

所以答案就是这个东西。

 

C:0次交换和1次交换的情况直接枚举,2次交换答案就是 (suma - ai1 - aj1 + bi2 + bj2) - (sumb - bi2 - bj2 + ai1 + ai2)考虑先 n^2 把所有可能选择的ai,aj,算出suma - 2*(ai + aj)并把这些东西排序,然后枚举每个bi,bj二分找出和 -2(bi+bj)算答案就可以了。

 

[czyz 2017.04.20 NOIP 模拟赛]