汽车加油问题------贪心思想
汽车加油问题 Description 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置，计算最少加油次数。 Input 输入数据的第一行有2 个正整数n和k（n≤5000，k≤1000），表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。 Output 将计算出的最少加油次数输出。如果无法到达目的地，则输出“No Solution!”。 Sample Input 7 7 1 2 3 4 5 1 6 6 Output 4
#include<iostream>
using namespace std;
int a[1010];
int main()
{
int n,k;
cin>>n>>k;
k+=1;
int f =1,tot =0,now =n;
while(k--)
{
int x;//预到达
cin>>x;
if(x>n)
{
f=0;
break;
}
else if(x> now)
{
tot++;
now =n-x;
}
else if(x <now)now -=x;
}
if(f)
cout<<tot<<endl;
else
cout<<"No Solution!"<<endl;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-05-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读