2622: 贪心算法-汽车加油问题
金币值：3
定数：6
时间限制：1.000 s
内存限制：128 M
正确：3
提交：3
正确率：100.00% 命题人：
题目描述
已知一辆汽车加满油之后可行驶 $n$ 公里，旅途中有 $k$（假设 $k \le 20$）个加油站(相邻两个加油站的距离小于等于 $n$)，出发之前汽车已经加满油。设计一个有效的贪心算法（贪心思想：加满油之后尽可能走过多个站点），指出应在旅途中的哪些加油站停靠加油，使沿途加油次数最少。
测试代码 复制
#include <stdio.h>
#include<stdlib.h>
int f(int dist[],int x[],int n,int k){ // 变量i表示第i-1个站点与第i个站点之间的第i个长度
int count=0; //记录加油的次数
int y=0; //记录上次加油之后已经走过的路程
for(int i=1; i<=k; i++){
if(y+dist[i]>n){
}else{
}
}
return count;
}
int main(void) {
int i,n,k; // n表示加满油之后最多可以行驶的距离，k表示沿图有k个加油站点
int dist[21]; //表示相邻两个站点之间的距离，0号单元不存储有效数据
int x[21]; //解向量，0号单元不存储有效数据，x[i]=0表示第i个加油站不加油，x[i]=1表示第i个加油站加油
scanf("%d %d",&n,&k);
for(i=1; i<=k; i++)scanf("%d",&dist[i]);
for(i=1; i<=k; i++)x[i]=0; //初始化旅途中各个站点都不加油
printf("%d\n", f(dist,x,n,k));
for(i=1; i<=k; i++)printf("%d ",x[i]);
return 0;
}输入格式
第一行输入两个正整数，分别表示 $n$ 和 $k$
第二行输入 $k$ 个正整数，分别表示相邻两个加油站之间的距离
第二行输入 $k$ 个正整数，分别表示相邻两个加油站之间的距离
输出格式
第一行输出最少的加油次数
第二行输出在哪些站点加油（$1$ 表示加油，$0$ 表示不加油，相邻两个数之间用一个空格隔开）
第二行输出在哪些站点加油（$1$ 表示加油，$0$ 表示不加油，相邻两个数之间用一个空格隔开）
输入样例 复制
70 8
10 20 30 40 50 10 60 60输出样例 复制
4
0 0 1 1 0 1 1 0