CF1854A1 Dual (Easy Version)

发布时间 2023-11-27 19:34:48作者: 梓熠帅哥

如果你是没有思路,但是还是想自己做出来,以下有几个提示(请看完一个提示之后,再想不出来再看接下来的提示)。

## 提示1

> 对于 easy version,有多种解决方案。不管是哪种解决方案,请思考:怎样得到 $a_i \le a_{i+1}$?

## 提示2

> 举个例子,你可以试着使用序列中的一个**正数**将 $a_{i+1}$ 变大。

> 但当所有数都是负数的时候,你该怎么办呢?

## 提示3

> 如果所有数都是负数的时候,你可以使用 $n-1$ 步取胜(请思考策略)。

> 如果在序列中**有至少一个正数**,你**就**可以做到 $a_1 \le a_2$,之后 $a_2 \le a_3$,等等。

## 提示4

> 用操作 $(i,i)$ 去构造一个**足够大的正数**(到底要多大呢),然后再让 $a_2$、$a_3$...变得更大(用这个足够大的正数)。

## 解决方法

> 如果序列中所有的数都是负数,你可以使用操作 $(n-1,n)$,$(n-2,n-1)$...来进行后缀和(它们是不递减的)。

> 如果序列中有至少一个正数 $a_x$。

> - 使用至多 5 次操作 $(x,x)$ 使得 $a_x > 20$。
> - 使用 2 次操作 $(2,x)$ 使得 $a_2$ 变成序列中最大的数。
> - 使用 2 次操作 $(3,2)$ 使得 $a_3$ 变成序列中最大的数。
> - ...

> 此策略可以在 $5+2(n-1) \le 43$ 步内完成要求。

> 时间复杂度:$O(n)$。

[参考代码](https://codeforces.com/contest/1854/submission/231106134)