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 ai 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),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 integersa1, 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.
4 1 1 2 1 5
2 + 3 2 - 4 1
4 1 1 2 3 4
0
题意:
给出 N,K(1 ~ 1000)。代表有N个数,输出要如何操作最少数,使整个序列满足 ai - ai-1 = k。输出最少操作数,后输出这些操作是什么。(操作 + 序号 + 个数)。每个数都必须 >= 0。
思路:
暴力。1000个数,每个数都扫一遍也就O(n^2)< 1s,果断暴搜。每个位置都向两边搜索一遍,同时比较最小操作数,若有数小于等于0则不取这个点。一开始没看到所有数都必须 >= 0,无限wa。
AC:
#include <stdio.h> #include <string.h> int num[1005],vis[1005]; int main() { int n,k,step = 9999,in; scanf("%d%d",&n,&k); for(int i = 1;i <= n;i++) scanf("%d",&num[i]); for(int i = 1;i <= n;i++) { int t = i,ans = 0,temp = 1; vis[t] = num[t]; while(t != 1) { if(num[t - 1] + k != vis[t]) ans++; vis[t - 1] = vis[t] - k; if(vis[t - 1] <= 0) { temp = 0; break; } t--; } if(!temp) continue; t = i; while(t != n) { if(vis[t] + k != num[t + 1]) ans++; vis[t + 1] = vis[t] + k; t++; } if(ans < step) { step = ans; in = i; } } printf("%d\n",step); int t = in; while(t != 1) { int ans = num[t - 1] + k - num[t]; if(ans > 0) printf("- %d %d\n",t - 1,ans); if(ans < 0) printf("+ %d %d\n",t - 1,-ans); num[t - 1] = num[t] - k; t--; } t = in; while(t != n) { int ans = num[t] + k - num[t + 1]; if(ans > 0) printf("+ %d %d\n",t + 1,ans); if(ans < 0) printf("- %d %d\n",t + 1,-ans); num[t + 1] = num[t] + k; t++; } return 0; }
相关推荐
Behavior Trees in Robotics&AI; A Behavior Tree (BT) is a way to structure the switching between different tasks1 in an autonomous agent, such as a robot or a virtual entity in a computer game. An ...
How to determine how many trees to use in a random forest Just where does the "randomness" come from Out of Bag Errors & Cross Validation - how good of a fit did the machine learning algorithm make...
In a single data structure, the GiST provides all the basic search tree logic required by a database system, thereby unifying disparate structures such as B+-trees and R-trees in a single piece of ...
The Second Edition of Joe Celko’s Trees and Hierarchies in SQL for Smarties covers two new sets of extensions over three entirely new chapters and expounds upon the changes that have occurred in SQL...
orchard plant problem data for 17 trees (4 trees pre row) total 14 rows
Behavior Trees in Robotics and AI: An Introduction
Efficient in-memory indexing with Generalized Prefix trees的PPT
Set Partitioning in Hierarchical Trees 英文文档,多级树集合分裂(SPIHT)算法
The oak trees were created using CTI whose tree shaders support (deferred) translucent lighting, advanced bending driven by a built in directional wind zone and smooth LOD transitions. Unity's ...
result for orchard plant problem with 17trees 4 trees per row
MK.Joe.Celkos.Trees.and.Hierarchies.in.SQL.for.Smarties
Classification and Regression Trees reflects these two sides, covering the use of trees as a data analysis method, and in a more mathematical framework, proving some of their fundamental properties.
英文版,世界著名的数据库专家,曾经担任ANSI SQL标准委员会成员达10年之久的作者所著代表作,关系数据库存储各种如图,树,二叉树等数据结构的实现及操作,如邻接表,先序遍历树等,虽不是新书,但个人认为是很经典...
Behavior Trees Library in C++. Batteries included..zip
B-Trees 的实现及分析 B-Trees 代码
ffl the Ford-Bellman Strategy for optimal paths in acyclic digraphs, ffl the Greedy Method for optimal forests and spanning trees in undirected graphs. In our general decision model, we define ...
权威又详细的空间树rtree论文 paper by Guttman
6_Concurrent rebalancing of AVL trees_A fine-grained approach
Amir Said和William Pearlman 写的SPIHT的源代码
Role of trees and forests in disaster risk reduction and mitigation