304916: CF933E. A Preponderant Reunion

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A Preponderant Reunion

题意翻译

哪里再好,都不如自己的家好。这就是为什么过农历新年全家团聚这么重要。 在吃完团圆饭后,Tommy和他的家人们玩了一个游戏,规则如下: 1.一开始有一个由非负整数组成的序列$n$。规定无论何时数列中的每个整数都是非负的。 2.你可以在这个序列里选择两个相邻的正整数$p_i$和$p_{i+1}(1\leq i\lt n)$,然后将每个数都减去他们中的最小值$(min(p_i,p_{i+1}))$,代价为$min(p_i,p_{i+1})$。我们将此称为一次操作。 3.当数列中没有两个相邻的正整数时,游戏结束。你的任务就是用最少的代价结束游戏。 很显然,最多$n-1$次操作后游戏就会结束。请你告诉我们最优解。 ## 输入格式 第一行是一个整数$n(1 \leq n \leq 3*10^{5})$。 第二行是$n$个整数$p_1,p_2,...,p_n(0 \leq p_i \leq 10^{9},i=1,2,...,n)$。 输出格式 第一行是一个整数$m(0 \leq m \leq n-1)$,代表操作的次数。 接下来$m$行按时间顺序输出你的操作:每行一个整数$i(1 \leq i \lt n)$代表对$p_i$和$p_{i+1}$进行如上操作。 若有多解,输出任一即可。

题目描述

East or west, home is best. That's why family reunion, the indispensable necessity of Lunar New Year celebration, is put in such a position. After the reunion dinner, Little Tommy plays a game with the family. Here is a concise introduction to this game: 1. There is a sequence of $ n $ non-negative integers $ p_{1},p_{2},...,p_{n} $ in the beginning. It is ruled that each integer in this sequence should be non-negative at any time. 2. You can select two consecutive positive integers in this sequence, $ p_{i} $ and $ p_{i+1} $ $ (1<=i&lt;n) $ , and then decrease them by their minimum (i. e. $ min(p_{i},p_{i+1}) $ ), the cost of this operation is equal to $ min(p_{i},p_{i+1}) $ . We call such operation as a descension. 3. The game immediately ends when there are no two consecutive positive integers. Your task is to end the game so that the total cost of your operations is as small as possible. Obviously, every game ends after at most $ n-1 $ descensions. Please share your solution of this game with the lowest cost.

输入输出格式

输入格式


The first line contains one integer $ n $ $ (1<=n<=3·10^{5}) $ . The second line contains $ n $ space-separated integers $ p_{1},p_{2},...,p_{n} $ $ (0<=p_{i}<=10^{9},i=1,2,...,n) $ .

输出格式


In the first line print one integer as the number of descensions $ m $ $ (0<=m<=n-1) $ . In the next $ m $ lines print the descensions chronologically. More precisely, in each line of the next $ m $ lines print one integer $ i $ $ (1<=i&lt;n) $ representing a descension would operate on $ p_{i} $ and $ p_{i+1} $ such that all the descensions could be utilized from top to bottom. If there are many possible solutions to reach the minimal cost, print any of them.

输入输出样例

输入样例 #1

4
2 1 3 1

输出样例 #1

2
1
3

输入样例 #2

5
2 2 1 3 1

输出样例 #2

3
2
1
4

说明

In the first sample, one possible best solution is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF933E/5514e1fc7d0b6064021e9d6d57147b2abc1b3686.png), of which the cost is $ 1+1=2 $ . In the second sample, one possible best solution is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF933E/0899cab2deb5ed7ca02595a7f99c5aba9588c34e.png), of which the cost is $ 1+1+1=3 $ .

Input

题意翻译

哪里再好,都不如自己的家好。这就是为什么过农历新年全家团聚这么重要。 在吃完团圆饭后,Tommy和他的家人们玩了一个游戏,规则如下: 1.一开始有一个由非负整数组成的序列$n$。规定无论何时数列中的每个整数都是非负的。 2.你可以在这个序列里选择两个相邻的正整数$p_i$和$p_{i+1}(1\leq i\lt n)$,然后将每个数都减去他们中的最小值$(min(p_i,p_{i+1}))$,代价为$min(p_i,p_{i+1})$。我们将此称为一次操作。 3.当数列中没有两个相邻的正整数时,游戏结束。你的任务就是用最少的代价结束游戏。 很显然,最多$n-1$次操作后游戏就会结束。请你告诉我们最优解。 ## 输入格式 第一行是一个整数$n(1 \leq n \leq 3*10^{5})$。 第二行是$n$个整数$p_1,p_2,...,p_n(0 \leq p_i \leq 10^{9},i=1,2,...,n)$。 输出格式 第一行是一个整数$m(0 \leq m \leq n-1)$,代表操作的次数。 接下来$m$行按时间顺序输出你的操作:每行一个整数$i(1 \leq i \lt n)$代表对$p_i$和$p_{i+1}$进行如上操作。 若有多解,输出任一即可。

加入题单

上一题 下一题 算法标签: