首页 > 试题广场 >

加油站良好出发点问题

[编程题]加油站良好出发点问题
  • 热度指数:1561 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
N个加油站组成一个环形,给定两个长度都是N的非负数组oil和dis(N>1),oil[i]代表第i个加油站存的油可以跑多少千米,dis[i]代表第i个加油站到环中下一个加油站相隔多少千米。假设你有一辆油箱足够大的车,初始时车里没有油。如果车从第i个加油站出发,最终可以回到这个加油站,那么第i个加油站就算良好出发点,否则就不算。请返回长度为N的boolean型数组res,res[i]代表第i个加油站是不是良好出发点
规定只能按照顺时针走,也就是i只能走到i+1,N只能走到1
[要求]
时间复杂度为,空间复杂度为

输入描述:
第一行一个整数N表示加油站数量。
第二行N个整数,表示oil数组。
第三行N个整数,表示dis数组。


输出描述:
输出N个整数。若第i个整数为0表示该位置不是良好出发点,为1表示该位置是良好出发点。
示例1

输入

9
4 2 0 4 5 2 3 6 2
6 1 3 1 6 4 1 1 6

输出

0 0 0 0 0 0 0 0 0
示例2

输入

8
4 5 3 1 5 1 1 9
1 9 1 2 6 0 2 0

输出

0 0 1 0 0 1 0 1

说明

如果车从A点出发,到B点且加上B的油,还剩8的油,发现到不了C;
如果从B点出发,发现车到不了C;
如果从C点出发,发现可以转一圈,所以C点是良好出发点。


备注:


头像 星晨
发表于 2020-11-28 20:41:14
常规解法 常规思路需要 O(n*n) 的时间复杂度 才能计算出来具体做法就是 穷举,从 0-n 不停的作为出发点测试 基于常规进行优化 模拟常规代码 for i~ n { can[i] = 0 for j=i;j<i+n;j++ { j = j %n 展开全文