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

A. Life of a Flower

按照题意模拟即可。

Java

C++

显然，当最大值位于数组的最右端时，数组不再发生变化。
而每次操作后，最右侧的值会变为从右往左第一个比当前最右端的值大的数。

因此我们只需要找出经过多少次操作后，最右端的值变为数组的最大值即可。

Java

C++

显然，除了最后一次送货之外，每次送货完成后都会需要返回原点。因此最后一次送货应当尽可能远一点。
同时，远处的送货应当尽可能带满货物。

因此我们从远到近，一次往返带货，最后我们再减去最后一次带货返回的路程即可。

Java

C++

首先如果有重复的数字，那么我们可以通过两个相同的数字加上一个不同的数字实现两个数字的互换位置。因此，如果有相同的数字，则一定是YES。

而对于没有重复数字的情况。我们可以观察到，每次操作之后，数组的逆序对数目只会变化2。比如[1,2,3,4,5]，我们对2,3,4执行操作后，变成了[1,4,2,3,5]，逆序对数目由0变成了2。
因此我们只需要用线段树维护出逆序对的数目即可，如果数目是偶数，则YES，否则NO。

Java

C++