Codeforces Round #236 (Div. 2) B. Trees in a Row

本文主要是介绍Codeforces Round #236 (Div. 2) B. Trees in a Row，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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?

Input

The first line contains two space-separated integers: n, k (1 ≤ n, k ≤ 1000). The second line contains n space-separated integersa₁, a₂, ..., a_n (1 ≤ a_i ≤ 1000) — the heights of the trees in the row.

Output

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.

Sample test(s) 
input 
4 1
1 2 1 5
output 
2
+ 3 2
- 4 1
input 
4 1
1 2 3 4
output 
0

第二题其实也挺简单的，我比较喜欢做这种数据要求很有规律并且很简单的题

首先遍历以每颗树为基准，判断需要改变树高度的次数

隐含的条件就是要保证以当前树为基准时别的树高度不能小于0

取最小的那次对应基准，再判断别的树需要怎样改变

代码如下：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#define  MAXN 1010
#define  INF 0x7FFFFFFF
#define  ll long long
using namespace std;
int a[MAXN], sum[MAXN];
int main(void){int n, k;while(cin >> n >> k){for(int i=0; i<n; ++i){cin >> a[i];}for(int i=0; i<n; ++i)sum[i] = 0;for(int i=0; i<n; ++i){for(int j=0; j<n; ++j){int t1 = a[i]+(j-i)*k;//第j棵树期望的高度 int t2 = a[j]-t1;if(t1 < 0){sum[i] = INF;//以i 为基准出现负数时，应该取消当前循环 break;}if(t2 != 0){sum[i]++;//以i为基准需要的改变次数 }}}int flag = 0;int min = INF;for(int i=0; i<n; ++i){if(sum[i] < min){min = sum[i];flag = i;}}//以flag为基准，移动最少cout << sum[flag] << endl;for(int i=0; i<n; ++i){int step = a[flag]+(i-flag)*k - a[i];if(step > 0){cout << "+ " << i+1 << " " << step << endl;}else if(step < 0){cout << "- " << i+1 << " " << -step << endl;}} }return 0;
}

这个代码也跪了。。。又是少了一个等号。。。t1<=0时都需要退出循环

代码如下：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#define  MAXN 1010
#define  INF 0x7FFFFFFF
#define  ll long long
using namespace std;
int a[MAXN], sum[MAXN];
int main(void){int n, k;cin >> n >> k;for(int i=0; i<n; ++i){cin >> a[i];}for(int i=0; i<n; ++i)sum[i] = 0;for(int i=0; i<n; ++i){for(int j=0; j<n; ++j){int t1 = a[i]+(j-i)*k;//��j��������ĸ߶� int t2 = a[j]-t1;if(t1 <= 0){sum[i] = INF;//��i Ϊ��׼���ָ���ʱ��Ӧ��ȡ��ǰѭ�� break;}if(t2 != 0){sum[i]++;//��iΪ��׼��Ҫ�ĸı���� }}}int flag = 0;int min = INF;for(int i=0; i<n; ++i){if(sum[i] < min){min = sum[i];flag = i;}}//��flagΪ��׼���ƶ�����cout << sum[flag] << endl;for(int i=0; i<n; ++i){int step = a[flag]+(i-flag)*k - a[i];if(step > 0){cout << "+ " << i+1 << " " << step << endl;}else if(step < 0){cout << "- " << i+1 << " " << -step << endl;}} return 0;
}

这篇关于Codeforces Round #236 (Div. 2) B. Trees in a Row的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！