在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 给定两个整数数组 gas 和 cost ,如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。 C语言
时间: 2023-05-28 20:07:12 浏览: 58
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
int start = 0, cur_gas = 0, total_gas = 0, total_cost = 0;
for(int i = 0; i < gasSize; i++){
total_gas += gas[i];
total_cost += cost[i];
cur_gas += gas[i] - cost[i];
if(cur_gas < 0){
start = i+1;
cur_gas = 0;
}
}
return total_gas >= total_cost ? start : -1;
}
相关问题
用c语言写代码:在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
以下是用C语言实现的代码:
```c
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
int totalGas = 0, currGas = 0, start = 0;
for(int i = 0; i < gasSize; i++){
totalGas += gas[i] - cost[i];
currGas += gas[i] - cost[i];
if(currGas < 0){ // 无法到达下一个加油站
currGas = 0;
start = i + 1;
}
}
return (totalGas >= 0) ? start : -1; // 如果总油量 >= 总消耗量,一定可以完成绕环路行驶一周
}
```
思路解析:
- 定义变量 `totalGas` 表示总油量与总消耗量之差。
- 定义变量 `currGas` 表示当前油量与当前消耗量之差。
- 定义变量 `start` 表示起点加油站的下标。
- 遍历所有的加油站,将油量和消耗量的差累加到 `totalGas` 和 `currGas` 中。
- 如果 `currGas` 小于 0,表示无法到达下一个加油站,则将 `currGas` 重置为 0,并将起点加油站的下标设置为当前加油站的下一个位置。
- 最后判断 `totalGas` 是否大于等于 0,如果是,则一定可以完成绕环路行驶一周,返回起点加油站的下标,否则返回 -1。
用C语言并根据贪心算法编写代码:在一条环路上有N个加油站,其中第i个加油站有汽油gas[i]升.你有一辆油箱容量无限的汽车,从第i个建有站开往第i+1个加油站需要汽油cost[i]升.你从其中的一个加油站出发,开始时油箱为空.如果你可以绕环路行使一周,则返回出发时加油站的编号,否则返回-1.
以下是基于贪心算法的 C 语言代码实现:
```c
#include <stdio.h>
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
int start = 0; // 起点
int totalGas = 0; // 总油量
int currGas = 0; // 当前油量
for (int i = 0; i < gasSize; i++) {
totalGas += gas[i] - cost[i]; // 计算总油量
currGas += gas[i] - cost[i]; // 计算当前油量
if (currGas < 0) { // 当前油量不足以到达下一个加油站
start = i + 1; // 将起点设置为下一个加油站
currGas = 0; // 当前油量清零
}
}
return totalGas >= 0 ? start : -1; // 如果总油量大于等于0,则可以绕环路行使一周,返回起点,否则返回-1
}
int main() {
int gas[] = {1, 2, 3, 4, 5};
int cost[] = {3, 4, 5, 1, 2};
int result = canCompleteCircuit(gas, 5, cost, 5);
printf("Result: %d\n", result);
return 0;
}
```
该算法的时间复杂度为 O(n),其中 n 为加油站数量。