【CCF认证】201812_2 小明放学

  • 时间:
  • 浏览:
  • 来源:互联网

参考文章 原博主的解法很妙!

算法设计
本题中红绿灯的变换顺序为
在这里插入图片描述

可以定义一个长度为3的数组light来存储红灯、绿灯、黄灯时长,令sum为红绿黄灯的总时长。注意由于k=1、2、3 时,分别表示出发时刻,红绿灯状态是红灯、黄灯、绿灯,需要当k == 1时,令k=0;当k==3时,令k=2,才能建立起k和数组light的映射关系。
关键是计算出小明到达某一个红绿灯时亮的是那种灯,以及该灯还能亮多长时间。假设初始时刻某一个红绿灯还能亮的时间为b,且该灯在数组light中的下标为a,那么该灯已经点亮的时间为light[a]-b。假设小明到达该灯时已经用时ans,那么到达该灯时,如果不变灯,该灯已经点亮时间为light[a]-b+ans。sum为红绿黄灯从红到绿再变黄最后转化到红灯,即红绿灯变换一圈的总时长,那么(light[a]-b+ans)%sum就表示该红绿灯变换的最后一周的时长。不妨令b=(light[a]-b+ans)%sum,若b比当前红绿灯时长长,就让b减去当前的红绿灯时长,并令a转向下一个红绿灯,如此反复,直到b比当前红绿灯时长短,那么当前的a就指向小明到达某一个红绿灯时亮的灯,b表示该灯已经点亮的时间。

注意点
要用long long存储数据,int存储会造成数据溢出
在这里插入图片描述
代码实现

#include<iostream>
typedef long long ll;
using namespace std;

ll n;
ll light[3]; // 红、绿、黄 
ll k,t; // 灯; 显示的数字 
ll ans;  

int main()
{
	cin>>light[0]>>light[2]>>light[1]; // 红、黄、绿
	ll sum = light[0] + light[1] + light[2]; // 一个周期时间 
	cin>>n;
	while(n--){
		cin>>k>>t;
		if(k==0){ // 路 
			ans += t;
		}
		else{ // 灯 
			if(k==1) k=0; // 红灯,转化为下标
			// 黄灯下标相同,无需处理 
			else if(k==3) k=1; // 绿灯,转化为下标
			t = (light[k]-t+ans)%sum; // t为以这个灯初始为起点后的时长(<sum)
			// 求此时的灯和已过去时间 
			while(t>=light[k]){  //若t比当前灯时长长
				t -= light[k]; //减去当前的灯时长
				k = (k+1)%3; //转向下一个灯 
			} 
			if(k==0) // 红灯 
				ans += light[k]-t; // 加上红灯剩余时长 
			else if(k==2) // 黄灯
				ans += light[k]-t+light[0]; // 加上黄灯和红灯 
	
		}
	}
	cout<<ans<<endl;
	return 0; 
}

本文链接http://www.dzjqx.cn/news/show-617010.html