CF402B.Trees in a Row
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The Queen of England has n trees growing in a row in her garden. At that, the i-th (1 ≤ i ≤ n) tree from the left has height a__i meters. Today the Queen decided to update the scenery of her garden. She wants the trees' heights to meet the condition: for all i (1 ≤ i < n), a__i + 1 - a__i = k, where k is the number the Queen chose.
Unfortunately, the royal gardener is not a machine and he cannot fulfill the desire of the Queen instantly! In one minute, the gardener can either decrease the height of a tree to any positive integer height or increase the height of a tree to any positive integer height. How should the royal gardener act to fulfill a whim of Her Majesty in the minimum number of minutes?
英国女王的花园中有一排共 n 棵树。其中,从左往右数第 i 棵(1≤i≤n)树的高度为 ai 米。今天,女王决定更新花园的景致,希望所有树的高度满足如下条件:对所有 i(1≤i<n),均有 ai+1−ai=k,其中 k 是女王选定的一个常数。
不幸的是,皇家园丁并非机器,无法瞬间实现女王的愿望!园丁每分钟最多可执行以下操作之一:将某棵树的高度降低至任意一个正整数高度,或将某棵树的高度升高至任意一个正整数高度。那么,园丁应如何操作,才能以最少的分钟数满足女王的心愿?
输入格式
The first line contains two space-separated integers: n, k (1 ≤ n, k ≤ 1000). The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 1000) — the heights of the trees in the row.
第一行包含两个用空格分隔的整数:n、k(1 ≤ n, k ≤ 1000)。第二行包含 n 个用空格分隔的整数 a1, a2, ..., an(1 ≤ ai ≤ 1000)—— 表示一行中各棵树的高度。
输出格式
In the first line print a single integer p — the minimum number of minutes the gardener needs. In the next p lines print the description of his actions.
If the gardener needs to increase the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, then print in the corresponding line "+ j x". If the gardener needs to decrease the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, print on the corresponding line "- j x".
If there are multiple ways to make a row of trees beautiful in the minimum number of actions, you are allowed to print any of them.
第一行输出一个整数 p —— 园丁所需的最少分钟数。接下来的 p 行输出其操作的描述。
若园丁需要将从左往右数第 j 棵树(1 ≤ j ≤ n)的高度增加 x(x ≥ 1)米,则在对应行中输出 + j x;
若园丁需要将从左往右数第 j 棵树(1 ≤ j ≤ n)的高度减少 x(x ≥ 1)米,则在对应行中输出 - j x。
如果存在多种方式能在最少操作次数下使树排成“美观”的形态,你可以输出其中任意一种方案。
输入输出样例
输入#1
4 1 1 2 1 5
输出#1
2 + 3 2 - 4 1
输入#2
4 1 1 2 3 4
输出#2
0
输入解题思路,AI测评打分。不知道怎么写?