CF 253C(找中转行)

Posted on by
内容目录
C. 光标移动
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

文本编辑器有n行，每行k个字符（显然光标有k+1个位置，标记为1..k+1.

有4个操作：

  • "Up": 光标将向上移1行，列不变。如果上一行字符太少，则光标跑到行末。

  • "Down":
    光标将向下移1行，列不变。如果上一行字符太少，则光标跑到行末。

  • "Right": 光标向右移1格，操作不能在行末进行。

  • "Left":
    光标向左移1格，操作不能在行首进行。

    求出把光标从 (r1, c1) 移向(r2, c2)最小步数.

    • Input

    第一行一个整数 n (1 ≤ n ≤ 100) . 第二行 n个整数a1, a2, ..., an (0 ≤ ai ≤ 105),
    表示每行字符数. 第三行4个整数 r1, c1, r2, c2 (1 ≤ r1, r2 ≤ n, 1 ≤ c1 ≤ ar1 + 1, 1 ≤ c2 ≤ ar2 + 1).

    Output

    输出最小步数

    Sample test(s)
    input
    4
2 1 6 4
3 4 4 2
    output
    3
    input
    4
10 5 6 4
1 11 4 2
    output
    6
    input
    3
10 1 10
1 10 1 1
    output
    3
    Note

    第一组数据若为

    123

    12

    123s567

    1t345

    则最小操作为 "Left", "Down", "Left".

    显然除了直接移(先行后列）外，

    唯一减少操作数的方法便是向中间以外的行数移，以求降低列的移动数。

    一定要注意不是挪到每行直接取abs(行尾-c2)的，因为可能会有往返行尾的路上有更小的，直接取行尾可能拉近它和c2的距离，但是这种操作是不可行的。

    #include<cstdio>
#include<functional>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (10000+100)
int a[MAXN],n;
int abs2(int a,int b)
{
	if (a<b) return b-a;
	else return a-b;
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int r1,c1,r2,c2;
	scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
	int mi=c1,ans=0,tans=1000000000;
	if (r1<r2)
	{
		ans=r2-r1;
		for (int i=r1+1;i<=r2;i++) mi=min(mi,a[i]+1);
		tans=min(tans,ans+abs(mi-c2));
		for (int i=r1-1,cost=2,mii=mi;i>=1;i--,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
		for (int i=r2+1,cost=2,mii=mi;i<=n;i++,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
	}
	else
	{
		ans=r1-r2;
		for (int i=r1-1;i>=r2;i--) mi=min(mi,a[i]+1);
		tans=min(tans,ans+abs(mi-c2));
		for (int i=r2-1,cost=2,mii=mi;i>=1;i--,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
		for (int i=r1+1,cost=2,mii=mi;i<=n;i++,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
	}
	cout<<tans<<endl;
	return 0;
}