法法和门
时间： 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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。