推了推不存在的眼镜)哈?就这?这种题目不是小学生都能做出来的吗?你居然还要我帮你分析代码?行吧行吧,看在你这可怜兮兮的份上,本大爷就大发慈悲地指点你一下。
1. 解题思路推导(扶额版)
第一步:理解题目本质
题目说“只有一盏灯是开的”——这不就是明摆着告诉你,其他灯都被按了偶数次,只有这盏倒霉蛋被按了奇数次吗?开关开关,按偶数次等于没按,按奇数次才改变状态。这么简单的道理,你不会现在才反应过来吧?
第二步:模拟操作过程
每次操作就是给一组编号的灯按一次开关。用数组cnt记录每盏灯被按的次数,初始都是0(关着的)。
对于每个操作(a,t),计算floor(k*a)(k=1到t),把对应位置的计数器+1。
这需要两层循环:外层遍历n次操作,内层遍历t次计算。
时间复杂度O(T),T最大200万,完全在可接受范围内——这种数据范围简直是送分题啊!
第三步:找出答案
最后遍历所有可能的灯编号(从1到MAX-1),找到第一个cnt[x]是奇数的位置,输出它。
因为题目保证有且只有一盏灯是开的,所以找到的第一个奇数就是答案。
什么?你问我为什么从1开始遍历?难道编号0的灯存在吗?不会吧不会吧,你不会连编号从1开始都不知道吧?
2. 代码注释(毒舌版)
最后补一刀:
你这代码写得也太直白了吧?简直就是“暴力模拟”四个字写在脸上。虽然对于这个数据范围来说确实能过,但一点技术含量都没有啊!下次能不能来点有挑战性的题目?这种题简直是浪费本大爷的脑细胞(虽然我根本没有脑细胞)!
虽然不想麻烦你,但给个赞吧!
此内容供参考,无情绪带入,切勿当真