悬关求助站外题
查看原帖
悬关求助站外题
502121
TryHardToBeAlive楼主2023/8/11 22:26

这道题是在Acwing上做到的,是Google Kickstart2022 Round H Problem A的题,但是我死活找不出问题,望大佬指教。

阿达正在一个长度为 L的环形跑道上练习跑步。

为了更专注于跑步,阿达专门准备了一台机器来统计她跑的圈数。

机器放置在跑道的起跑线上,从 0 开始计数。

每当阿达离开起跑线时(直接越过起跑线或在起跑线位置处改变方向并离开起跑线),她的面朝方向就会被机器记录。

机器只会实时记录她最近一次离开起跑线时的面朝方向。

每当阿达到达起跑线位置时,只要其面朝方向与机器记录的上次离开起跑线时的面朝方向相同,机器计数就会加 1 。

阿达从起跑线处开始跑步。

她的耐力有限,无法将计划的训练量一口气完成。

因此,每跑一段距离,她都会原地休息一段时间,用来恢复体力。

不幸的是,阿达的记忆力并不是很好,每当她休息完再次开始跑步时,她都会忘了之前面朝的方向。

这时,她只能随意选择一个方向(顺时针或逆时针),并面朝该方向从她停下的位置开始继续跑步。

具体的说,她一共进行了 N 段跑步,其中第 i 段跑步的距离为 Di ,跑步时的面朝方向为 Ci 。

请你计算,在阿达完成跑步后,机器最终记录的圈数。

输入格式 第一行包含整数 T ,表示共有 T 组测试数据。

每组数据第一行包含两个整数 L,N 。

接下来 N 行,每行包含一个整数 Di 和一个字符 Ci ,分别表示阿达一段跑步的距离和面朝方向。Ci 只可能是 C(表示顺时针方向)或 A(表示逆时针方向)。

输出格式 每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 x 为组别编号(从 1 开始),y 为一个非负整数,表示机器最终记录的圈数。

数据范围 1≤T≤100 , 1≤L≤109 , 1≤N≤104 , 1≤Di≤109 。

我的代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
int T,n,l;
int d[N];
int dis=0; //最近一次跑离起点所走的距离
char c[N]; //C顺A逆
char mc; //机器记录的方向
int ans=0;

void init(){
	memset(d,0,sizeof d);
	ans=0;
	dis=0;
}

signed main(){
	cin>>T;
	for(int t=1;t<=T;t++){
		init();
		cin>>l>>n;
		for(int i=1;i<=n;i++){
			cin>>d[i]>>c[i];
		}
		mc=c[1];
		for(int i=1;i<=n;i++){
			if(mc==c[i]){ //与上次方向相同则增加距离
				dis+=d[i];
			}else{ //不同则往回走
				int dist=dis-d[i];
				if(dist<0){ //小于0说明直接原路返回到了起点然后还反方向走了不少
					mc=c[i]; //那么更新方向
					dis=abs(dist); //并更新距离
				}else{
					dis=dist; //否则就减路程
				}
			}
			if(dis>=l){ //达到一圈
				dis-=l; //归零
				ans++;
			}
		}
		printf("Case #%lld: %lld\n",t,ans);
	}
	return 0;
}
2023/8/11 22:26
加载中...