若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1745: 汽车加油问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,358

题目描述

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产生一个最优解。

对于给定的n和k个加油站位置,计算最少加油次数。

输入

输入数据的第一行有2 个正整数n和k(n≤5000,k≤1000),表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 个整数,表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地,汽车已加满油。第k+1 个加油站表示目的地。

输出

将计算出的最少加油次数输出。如果无法到达目的地,则输出“No Solution!”。

样例输入

7 7
1 2 3 4 5 1 6 6

样例输出

4

参考代码

#include<stdio.h>
int minmin(int a,int b) 
{
    if (a>=b) return b; else return a;
}
int main() 
{
    int n,k,dis[1010],i,j,min=20000,num,time=0;
    long long int sum=0;
    scanf("%d %dn",&n,&k);
    for (i=1;i<=k+1;i++)
       {
        scanf("%d",&dis[i]);
        if (dis[i]>n) {printf("No Solution!");return 0;}
       sum+=dis[i];
       }
       num=n;
       for (i=1;i<=k+1;i++)
        if (num>=dis[i]) num=num-dis[i];
        else {num=n-dis[i];time=time+1;}
        if (sum<=n) time=0;
            printf("%d",time);
            return 0;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist