Codeforces Round #746 ABCD 题解 (Java/C++)

A. Gamer Hemose

题解

显然我们只需要选择攻击力最大的两个武器交替攻击即可。

代码

Java

C++

B. Hemose Shopping

题解

考量三个数a[i],a[j],a[k]。假设i<j<k，且$j-i\geq x$。我们可以做以下操作来实现这三个数的任意互换：

因此，如果[x, n-1]和[0, n-1-x]这两个区间有交集，那么毫无疑问，一定可以将整个数组重新排序。
如果x>n-1，也就是没有可排序的区间，那么整个数组都无法重新排序。
而在上面两种极端情况的中间，[x, n-1]和[0, n-1-x]显然是可以各自重新排序的。但考虑到a[0]可以随时和a[n-1]交换，所以除了[n-1-x, x]之间无法排序之外，其他区间都可以任意排序。

综合上面三种情况，我们得到结论，有且只有[n-1-x, x]这个区间无法排序。（这个区间可能是个无效区间，如第一种情况。也可能是整个区间，如第二种情况。）
我们只需要看排序后发生值发生变化的下标是否落在无法排序的区间内即可。