加油站良好出发点问题

加油站良好出发点问题

题目描述

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

[要求]

时间复杂度为$O(n)$，空间复杂度为$O(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点是良好出发点。
……

备注：

$1⩽N⩽10^5$
$0⩽oil[i],dis[i]⩽10^9$

题解：

贪心的思想。我们设置一个区间 [start, end) ，表示车可以从 start 开始，达到 end 的前一个位置。其中 start 我们任意挑选一个 $oil[i]>=dis[i]$ 的位置开始，而 $end=(start+1)$，若车能到达，表明可以走完一圈。我们可以提前利用：$oil[i]-dis[i]$记录每个车站剩下的油量。

从 start 开始遍历，使用一个变量 rest 记录剩余的油量，初始值为 $oil[start]-dis[start]$：

• 若 rest >= 0，尝试扩展 end ，即：$ret+=oil[end];end=(end+1)$；
• 若 rest < 0，向 start 左边扩展，尝试查看上一个车站能否补充现在的差额，即：$start=(start-1+n)$；
• 当 start == end 时停止；

若最终 rest >= 0​ ，说明 start 是一个良好出发点。对于剩下的点，我们从 start 开始往左边移动：

• 若 rest >=0 ，说明当前位置是一个良好出发点，往左移动，继续判断上一个点，即：start = (start - 1 + n) % n; rest = oil[start]；
• 否则，当前位置不是一个良好出发点，往左寻找可能补充差额的站，即：start = (start - 1 + n) % n; rest += oil[start]；

代码：

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100000;
int oil[N];
int dis[N];
bool ret[N];
int main(void) {
int n;
scanf("%d", &n);
for ( int i = 0; i < n; ++i )
scanf("%d", oil + i );
int st = -1, ed;
for ( int i = 0; i < n; ++i ) {
scanf("%d", dis + i);
oil[i] -= dis[i];
if ( oil[i] >= 0 ) st = i;
}
if ( st == -1 ) {
for ( int i = 0; i < n; ++i )
printf("%d%c", ret[i], " n"[i == n - 1]);
return 0;
}
ed = (st + 1) % n;
LL rest = oil[st];
while ( st != ed ) {
if ( rest >= 0 ) {
rest += oil[ed];
ed = (ed + 1) % n;
} else {
st = (st - 1 + n) % n;
rest += oil[st];
}
}
if ( rest >= 0 ) {
for ( int i = 0; i < n; ++i ) {
if ( rest >= 0 ) {
ret[st] = 1;
st = (st - 1 + n) % n;
rest = oil[st];
} else {
ret[st] = 0;
st = (st - 1 + n) % n;
rest += oil[st];
}
}
}
for ( int i = 0; i < n; ++i )
printf("%d%c", ret[i], " n"[i == n - 1]);
return 0;
}

最后

以上就是无情树叶为你收集整理的加油站良好出发点问题的全部内容，希望文章能够帮你解决加油站良好出发点问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。