法法和门

法法和门

时间: 1ms        内存:128M

描述:

在一张二维的地图上,对角线的两边是两个皇宫,对角线上的整点处设有门,
穿过门时要付1元的过门费,主人公从(0,0)点开始按照给你的路径开始行走,求出主人公需要付的银币数。(‘U’表示向上行走,’R’表示向右行走)。


红色箭头表示主人公的行走路线,绿色的门代表主人公必须支付银币的大门。

输入:

n(1<=n<=1e5)表示给出字符串长度,记下来一行给出长度为n的一个字符串表示主人公的行走路线。

输出:

一个整数,表示主人公需要支付银币的个数。

示例输入:

6
RURUUR

示例输出:

1

提示:

参考答案(内存最优[1120]):

#include <stdio.h>
int main()
{
    int i=0,j=0,money=-1,n,a,b=0;//a为当前所在皇宫,b为行走前所在皇宫
    char direction;
    scanf("%d",&n);
    getchar();
    while((direction=getchar())!=EOF)
    {
        if(direction=='U')
            i++;
        if(direction=='R')
               j++;


        if(i>j)
            a=1;
        if(i<j)
            a=2;
        if(a!=b)
            money++;
        b=a;



    }
    printf("%d",money);
    return 0;
}

参考答案(时间最优[2]):

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+7;
//int b[maxn][maxn];
int main()
{
    int n;
    char a[maxn];
    cin>>n;
    int ans=0;
    int x=0,y=0;
    scanf("%s",a);
    for(int i=0;i<n;i++)
    {
        if(a[i]=='R')
        {
            x++;
        }
        else
        {
            y++;
        }
        if(x==y)
        {
            if(a[i]==a[i+1])
                ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注