首页 > 其他 > 详细

CCF 考试 红绿灯放学时间计算

时间:2019-09-14 12:08:47      阅读:64      评论:0      收藏:0      [点我收藏+]

  • 题目分析
经过数段路,每段路开始至多有一个红绿灯,?? 由红黄绿三色构成,红灯和黄灯亮时禁行,绿灯亮时通行。绿灯闪烁完后短暂的黄灯,随后红灯禁行。本题目给出的是 红黄绿三色灯的点亮时间,n行k t ,k代码包括0 1 2 3 分别指示当前灯的状态。k==0时,表示通行路段所需时间t;k=1 2 3 ,t分别表示灯在当前状态显示剩余时间。给出出发时刻各个路口灯的状态以及通过路段所需时间,计算达到终点所需时间。
 
技术分享图片
图1. 三色循环示意图
模拟时间流逝,求出在i路口(0<=i<=n)通过时灯的状态。由于灯是三色循环的,假设三色状态总时间为sum,那么以i路口灯的刚开始亮时为时间线起点刻画数轴,如图2所示。假设已经流失时间为ans,此时i路口灯的坐标pos = ans + ( light_i - t),light_i 为路口灯状态持续最大时长。pos = pos % sum 即为循环转移最后一圈内的坐标,该坐标应处于0~sum之间。为了求出具体的灯状态,分别判断pos与三种状态的时长即可,每次判断时,若pos>light_i,则令pos = pos - light_i,同时灯状态转移到下一个即 i++,循环执行,直到pos小于light_i,表明当前位置所在状态已找到,即i。
 
技术分享图片
图2. 状态循环显示图
找到状态i后,判断三种情况即可,绿灯直接通过,红灯等待到绿灯出现即加上显示剩余时间,黄灯则要加显示剩余时间与红灯持续时间。
算法注意:
t 最大106 为避免溢出,所有涉及t的变量类型设置为long long类型

完整代码如下:
 
#include <iostream>
#define LOCAL
using namespace std;
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    long long light[3] = {0}, ans = 0, n, pos, sum; // 注意初始化的变量要赋值0
    // 红绿灯的变化范围为红绿黄 三色循环
    while(scanf("%lld%lld%lld", &light[0], &light[2], &light[1])==3){
        scanf("%lld", &n);
        sum = (light[0]+light[1]+light[2]);
        while(n--){
            long long k,t;
            scanf("%lld%lld",&k,&t);
            if (k==0){
                ans+=t;
            }else{
                if(k==1){
                    // 起始位置 此路段的灯为红 在light数组下标为0
                    k=0;
                }else if(k==3){
                    // 灯为绿色 在light数组下标为1
                    k=1;
                }
                // 模拟时间流逝
                // 将红绿黄灯刻在时间线上,时间线坐标起始位置是红灯开始的。 pos 就是 light[k]-t 加上运动的总时间
                // pos%sum 即为最后循环一周所在坐标 方便寻找状态
                pos = (light[k]-t + ans)% sum;
                // 寻找pos在哪个状态
                while(pos>light[k]){
                    pos = pos-light[k];
                    k = (k+1)%3;   // 三个灯循环后移
                }
                // 如果当前模拟到的状态为红灯 等待一段时间
                if(k==0){
                    ans += light[k]-pos;
                }else if (k==2){
                    // 黄灯
                    ans += light[k]-pos + light[0];
                }
            }
        }
        printf("%lld", ans);
    }
    return 0;
}

CCF 考试 红绿灯放学时间计算

原文:https://www.cnblogs.com/bicyclelg/p/11518606.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!