mary_yoyo 2023-03-15 18:34 采纳率: 100%
浏览 54
已结题

编程求解<闪烁灯泡>

C++编程求解

描述
马上就要迎来新年了,小A为了装饰自己的房间,决定在新年那一天挂起彩灯,已知彩灯每隔一分钟就会闪烁一下,闪烁的规律如下:
第一次只亮第1只灯
第二次只亮第3只灯
第三次只亮第6只灯
第四次只亮第10只灯,以此类推…
注意:彩灯是环状的,也就是说,如果只有5只灯泡,那么第6只就是第1只。
请问经过x分钟之后有哪些灯没有亮过,如果所有灯都亮过,请计算亮的次数最多灯泡是几号。

输入
一行,两个整数,分别表示灯泡的个数m(1≤ m ≤1000)m(1≤m≤1000)和经过的分钟n(1≤ n ≤10000)n(1≤n≤10000)

输出
如果有灯泡没亮,那么输出所有没有亮过的灯泡编号;如果所有灯泡都亮过,那么输出亮的次数最多的灯泡编号(如果存在多个灯泡,输出编号最小的那只)。

输入样例 1

10 4

输出样例1

2 4 5 7 8 9

  • 写回答

1条回答 默认 最新

  • inferior_hjx 2023-03-15 20:38
    关注

    观察亮灯的规律,如下:

    原数组:1 3 6 10
    作 差: 1 2 3 4

    发现原数组的差分数组是等差数列。

    直接模拟即可,时间复杂度 O(n) .

    #include <bits/stdc++.h>
    using namespace std;
    int n, m, vis[10005];// vis[i] 记录第 i 盏灯亮了多少次
    int main() {
        scanf("%d%d", &m, &n);
        for (int i = 1, d = 1, now = 1; i <= n; i++, d++, now += d) {// d 是差值,也就是说下一次 now 要加上 d,now 是当前的位置
            if (now > m) now -= m;// now 超过了 m,要回去
            vis[now]++;//统计第 now 盏灯出现的次数
        }
        int fl = 0, mx = 0;
        for (int i = 1; i <= m; i++)
            if (!vis[i]) fl = 1;//第 i 盏灯没有亮过
            else if (vis[mx] < vis[i]) mx = i;//求出现次数最多的灯
        if (!fl) printf("%d", mx);//所有灯都亮过了
        else//有灯没亮过
            for (int i = 1; i <= m; i++)
                if (!vis[i])
                    printf("%d ", i);
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 3月27日
  • 已采纳回答 3月19日
  • 创建了问题 3月15日

悬赏问题

  • ¥15 找一个QT页面+目标识别(行人检测)的开源项目
  • ¥15 有没有整苹果智能分拣线上图像数据
  • ¥20 有没有人会这个东西的
  • ¥15 cfx考虑调整“enforce system memory limit”参数的设置
  • ¥30 航迹分离,航迹增强,误差分析
  • ¥15 Chrome Manifest扩展引用Ajax-hook库拦截请求失败
  • ¥15 用Ros中的Topic通讯方式控制小乌龟的速度,走矩形;编写订阅器代码
  • ¥15 LLM accuracy检测
  • ¥15 pycharm添加远程解释器报错
  • ¥15 如何让子窗口鼠标滚动独立,不要传递消息给主窗口