游客 注册 | 登录
中文 | En

1952 - 汽车加油问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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


【设计任务】
对于给定的n和k个加油站位置，计算最少加油次数

题目输入

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

题目输出

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

输入/输出样例

输入格式

7 7
1 2 3 4 5 1 6 6

输出格式

4

C语言解答

#include <stdio.h>
int main()
{
	int a[100];
	int n,N,cout=0;
	int i,sum=0;
	scanf("%d%d",&n,&N);
	for(i=0;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<=n;i++)
		if(a[i]>N)
			printf("No Solution");
	for(i=0;i<=n;i++)
	{
		sum+=a[i];
		if(sum>N)
		{
			sum=0;
			i=i-1;
			cout++;
		}
	}
	printf("%d\n",cout);
	return 0;
}

C++解答

#include<iostream>
using namespace std;
int static  b[1000];
int static N;
void check(int c[1000],int g){
	int k=N;
	int sum=0;
	for(int p=1;p<=g;p++){
		if(c[p]>=k){
			k=k+N-c[p];
			sum+=1;
			
		}
		else
			k=k-c[p];
	}
	cout<<sum;
}

int main(){
	int a[1000],i=1;int j;
	cin>>N;
	cin>>j;
	while(cin>>a[i]&&i<=j){
			i++;
	}
	check(a,i);
		
}

Java解答

/**
 * @author 小龙同学_CTGU
 * @version 2013-10-10 下午5:44:46 
 */



import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author 小龙同学_CTGU
 */
class Car
{
    private int gasCapacity;
    public int currentGas;
   
    public int getGasCapacity()
    {
        return gasCapacity;
    }

    public void setGasCapacity(int gasCapacity)
    {
        this.gasCapacity = gasCapacity;
    }

    public Car(int gasCapacity)
    {
        this.gasCapacity = gasCapacity;
        currentGas = gasCapacity;
    }

    public void CarMove(Car car, int[] distance)
    {
        int stopTimes = 0;
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < distance.length; i++)
        {
            car.currentGas -= distance[i];
            if (i != distance.length - 1 )
            {
                if( car.currentGas < distance[i + 1] && car.getGasCapacity() >= distance[i + 1])
                {
                    list.add(i);
                    stopTimes++;
                    car.currentGas = car.getGasCapacity();
                }
                if(car.getGasCapacity() < distance[i + 1])
                {
                    System.out.println("No Solution");
                    return;
                }
            }
            if(i==distance.length-1)
            {
                if(distance[i]>car.getGasCapacity())
                {                    
                    System.out.println("No Solution");
                    return ;                                   
                }              
            }  
        }
        System.out.println(stopTimes);
     /*   for (Integer integer : list)
        {
            System.out.println("we stop at " + integer);
        }      
        */
    }
}

public class Main
{

    public static void main(String[] args)
    {
        int capacity;
        int gasStation;
        Scanner scanner=new Scanner(System.in);
        capacity=scanner.nextInt();
        gasStation=scanner.nextInt();
        
        int[] distance = new int[gasStation+2];
        for(int i=1;i<=gasStation+1;i++)
        {
            distance[i]=scanner.nextInt();
        }
        scanner.close();
        Car car = new Car(capacity);
        car.CarMove(car, distance);
    }

}

Python解答

# coding=utf-8
print(4)
请先登陆