本文共 4672 字，大约阅读时间需要 15 分钟。
C. Text Editor
time limit per test
1 second
memory limit per test
256 megabytes
input
input.txt
output
output.txt
Vasya is pressing the keys on the keyboard reluctantly, squeezing out his ideas on the classical epos depicted in Homer's Odysseus... How can he explain to his literature teacher that he isn't going to become a writer? In fact, he is going to become a programmer. So, he would take great pleasure in writing a program, but none — in writing a composition.
As Vasya was fishing for a sentence in the dark pond of his imagination, he suddenly wondered: what is the least number of times he should push a key to shift the cursor from one position to another one?
Let's describe his question more formally: to type a text, Vasya is using the text editor. He has already written n lines, the i-th line contains ai characters (including spaces). If some line contains k characters, then this line overall contains (k + 1) positions where the cursor can stand: before some character or after all characters (at the end of the line). Thus, the cursor's position is determined by a pair of integers (r, c), where r is the number of the line and c is the cursor's position in the line (the positions are indexed starting from one from the beginning of the line).
Vasya doesn't use the mouse to move the cursor. He uses keys "Up", "Down", "Right" and "Left". When he pushes each of these keys, the cursor shifts in the needed direction. Let's assume that before the corresponding key is pressed, the cursor was located in the position (r, c), then Vasya pushed key:
You've got the number of lines in the text file and the number of characters, written in each line of this file. Find the least number of times Vasya should push the keys, described above, to shift the cursor from position (r1, c1) to position (r2, c2).
Input
The first line of the input contains an integer n (1 ≤ n ≤ 100) — the number of lines in the file. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 105), separated by single spaces. The third line contains four integers r1, c1, r2, c2(1 ≤ r1, r2 ≤ n, 1 ≤ c1 ≤ ar1 + 1, 1 ≤ c2 ≤ ar2 + 1).
Output
Print a single integer — the minimum number of times Vasya should push a key to move the cursor from position (r1, c1) to position (r2, c2).
Examples
input
Copy
42 1 6 43 4 4 2
output
Copy
3
input
Copy
410 5 6 41 11 4 2
output
Copy
6
input
Copy
310 1 101 10 1 1
output
Copy
3
Note
In the first sample the editor contains four lines. Let's represent the cursor's possible positions in the line as numbers. Letter s represents the cursor's initial position, letter t represents the last one. Then all possible positions of the cursor in the text editor are described by the following table.
123
12
123s567
1t345
One of the possible answers in the given sample is: "Left", "Down", "Left".
上次比赛没有做出来，现在想明白了。
【题意】
给定四种操作，求光标从一个点移动到另一个点需要的最小步数。
【方法】
贪心，求光标从特别长的一行到特别短的一行的最短路径，枚举每一行，分别求出最短路径，最后比较出结果。
AC
#include#include #include using namespace std;int a[105];int n;int ans=1<<30,up,down,c;int main(){ /*freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);*/ cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]++;//光标是在间隙，加1； } int r1,c1,r2,c2; cin>>r1>>c1>>r2>>c2; for(int i=1;i<=n;i++)//假设必须要到这一行 { up=min(i,min(r1,r2)); down=max(i,max(r1,r2)); c=c1; for(int j=up;j<=down;j++) { c=min(c,a[j]); } int sum=abs(i-r1)+abs(i-r2)+abs(c-c2); ans=min(ans,sum); } cout< <
转载地址：http://jmyzi.baihongyu.com/