问题描述
一辆汽车加满油后可行驶nkm 。旅途中有k个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并计算最少加油次数。
问题分析
根据贪心算法的贪心选择性质, 为了要使加油次数最少，就会选择离加满油的点远一点的加油站加油。
另外，当加满油之后，都要是此后的过程中使加油次数最少。每一次汽车中剩下的油不能再行驶到下一站时，就在该站加油。每一次加满油之后与起点具有相同的条件，可以看做一个新的起点，过程也是相同的。因此，该问题具有最优子结构性质
核心代码
nt
greedy(vector
<int> x
, int n
)
{
int j
, i
, s
, sum
=0, k
=x
.size();
for(j
=0; j
<k
; ++j
)
if(x
[j
] > n
) {
cout
<<"No Solution"<<endl
;
return -1;
}
for(i
=0, s
=0; i
<k
; ++i
) {
s
+= x
[i
];
if(s
> n
) sum
++, s
= x
[i
];
}
return sum
;
}
n:表示汽车加满油之后可以行驶nkm；k：旅途中有k个加油站
例子
加油站数：7 最大行驶距离：7 每个站之间的距离：1 2 3 4 5 1 6 6
红色部分表明要在从前一个加油站不能行驶到当前加油站，需在前一个加油站加油。 一共需要加油4次
完整代码
#include
<iostream>
using namespace std
;
int main()
{
int n
,k
;
int a
[100];
cout
<<"请输入最大行驶路径和站点个数：";
cin
>>n
>>k
;
int num
=0,s
=n
;
cout
<<"请输入每个站点之间的路径：";
for(int i
=0;i
<=k
;i
++)
{
cin
>>a
[i
];
}
for(int i
=0;i
<=k
;i
++)
{
if(a
[i
]>n
)
{
cout
<<"No Solution";
return 0;
}
if(s
-a
[i
]>=0)
{
s
-=a
[i
];
}
else
{
num
++;
s
=n
-a
[i
];
}
}
cout
<<"需要加油次数："<<num
;
return 0;
}
测试样例
输入 请输入最大行驶路径和站点个数：7 7 请输入每个站点之间的路径：1 2 3 4 5 1 6 6
输出 需要加油次数：4
