本文从WordPress迁移而来, 查看全部WordPress迁移文章
A.给出n,下面2n个实数,保证实数的输入,小数位都是3位。每次选取一个i,j(每个i,j只能被选一次,且i!=j,对i和j的大小无要求),将a[i]取下整,a[j]取上整,最后的结果就是2n个数字里面一半的数字取下整一半取上整,然后算一个绝对值 | (原本实数和) - (一半下整数和一半上整数的和) | , 使得绝对值最小
左式 = 实数和
右式 = 所有数字都取下整的和
绝对值 = | 左式 - 右式 |
显然右式是不符合要求的,还要将其中n个数字变为上整数。而原本的数字里面,其实只分了两类。
一类,将其从下整变为上整,数值是不变的(原本小数部分为0)
另一类,将其从下整变成上整,数值增加1(原本小数部分不为0),统计这类数字都多少个,COUNT
COUNT <= n的时候,最多只能选出COUNT个这类数字变为上整,至于具体选几个,枚举一次即可
COUNT > n的时候,至少要选出delta = COUNT-n个这类数字变为上整,必选之后,可选的余地,应该是n-delta个,具体还需要再选几个,枚举一次即可
其实就是,先全部取下整,那一些变为上整,一边变化,一边观察绝对值是否在一直变小,如果在某次变化过程中,绝对值反而越变越大了,那么就马上停止
因为输入数据保证小数3位,而输出也要保证小数3位,为了避免精度,整个程序都是转化为整数来处理的
1 |
|
B: J会交换相邻的两个数字,但是F会投硬币,正面的话,他会交换一个逆序对(两个数字要相邻),反面的话,他会交换一个顺序对(两个数字要相邻),游戏的结束是整个序列变升序。J以最优策略交换,问在F的影响下,游戏结束的数学期望是多少
题解为,F投到正面和反面的概率相同,要么交换逆序对要么交换顺序对,其实F做的工作是相互抵消的,所以只需要考虑J的工作即可,J的任务就是以最优策略,每次交换一对相邻的数字,使序列变为升序,这个步数,其实就是逆序对;以前接触过这个结论差点忘记了,其实J交换的策略就是,先把最大的那个数字,一次次地轮换到最后的位置,然后把次大的数字一次次地轮换到次后的位置……最后把最小的数字换到了第一位,这里的步数就是序列的逆序对
然后,逆序对为偶数的话,ans = n 2,逆序对为奇数的话,ans = n 2-1
1 |
|
写了个暴力的程序,按照题意来模拟了一次,发现结果和答案是一样的
1 |
|