「CF402B」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 aimeters. Today the Queen decided to update the scenery of her garden. She wants the trees’ heights to meet the condition: for alli (1 ≤ i < n), ai + 1 - ai = 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?
The first line contains two space-separated integers: n, k (1 ≤ n, k ≤ 1000). The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ 1000) — the heights of the trees in the row.
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.
|
1 2 |
4 1 1 2 1 5 |
|
1 2 3 |
2 + 3 2 - 4 1 |
|
1 2 |
4 1 1 2 3 4 |
|
1 |
题解
被坑了，这题要枚举第一个的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k,ans,mn=0x7fffffff; int a[1001]; int work(int x) { int s=0; for(int i=1;i<=n;i++) if(a[i]!=x+(i-1)*k)s++; return s; } void print() { for(int i=1;i<=n;i++) if(a[i]<ans+(i-1)*k)printf("+ %d %d\n",i,ans+(i-1)*k-a[i]); else if(a[i]>ans+(i-1)*k)printf("- %d %d\n",i,a[i]-ans-(i-1)*k); } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=1000;i++) { int t=work(i); if(t<mn){mn=t;ans=i;} } printf("%d\n",mn); print(); return 0; } |
OI 课件=>
