Codeforces Round #653 (Div. 3)

作者: ffacs 分类: Codeforces 发布时间: 2020-07-02 20:27

E2

题意

有 $n$ 本书,两个人,对每一本书,每个人都有喜欢或者不喜欢,看一本书的时间为 $t_i$ ,求选 $m$ 本书,两个人各至少喜欢其中的 $k$ 本书,且总时间最小.输出总时间和下标

解法

首先将书按两个人的喜欢情况分成四类再各自排序,先枚举选多少两个人都喜欢的书.那么就知道至少还要选多少只有一个人喜欢的书了.接下来就是要满足 $m$ 本书的条件.即从三个集合中取和最小的书.这可以用二分求出最大值的最小值是多少.剩下就是一些细节了

F

题意

规定一个操作为 $(a_i,a_{i+1},a_{i+2}) \rightarrow (a_{i+2},a_{i},a_{i+1})$ .问能否使用不超过 $n^2$ 次操作使得数组 $a$ 变成不降序,如果可以输出每次操作的 $i$

解法

我们可以用一次这个操作将一个数向前移动2,也可以连续用两次这个数往前移动1,我们显然就可以使除了最后两个数的部分有序.那么我们可以给每个数都重新分配值,使其变成一个排列.只要将这个排列排序即可.如果没有值重复那么直接按大小分配即可.否则还要考虑同个值之间的关系,因为我们不确定这是否会有影响.那么就要对这个操作进行深入的挖掘.我们发现如果是一个排列的话,使用这个操作之后 逆序对的奇偶性 不发生改变.也就是说,如果我们分配成排列之后,它逆序对要是偶数.这样我们就可以先排序,再赋值,如果逆序对是偶数的话,交换一对值相同的即可.我们交换他们即可.这样就改变了逆序对的奇偶.

发表评论

电子邮件地址不会被公开。 必填项已用*标注