游客 Signup | Login
中文 | En

2664 - 雨中外卖

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

最近白云校区大雨连连，导致在教学楼不能到饭堂就餐的学生也明显增多，他们采用电话预定的方式向饭堂订饭。

小明是饭堂勤工俭学的学生，他负责把饭送到教学楼。他有一辆自行车，一次可以放M个盒饭。总共有N栋教学楼在马路边一字排开，与饭堂在一条直线上，假设饭堂在原点，每栋教学楼之间的间隔都一样，第1栋教学楼与饭堂的距离与教学楼之间的间隔也一样。现在饭堂收到每栋教学楼学生订餐的饭盒数分别为 a1, a2, a3..., an。 请帮小明制定一个最快送饭的方案。 


假设小明 经过两栋教学楼的距离所用时间是10分钟，每栋楼交付一个饭盒所需要的时间是15秒。

Input

有多组测试用例，

每组用例有两行输入，第一行是两个正整数 M N （M<50,  N<100），

第二行是N非负整数a1  a2  a3 ...


Output

每行输出每组测试用例的完成时间，表示小明送完全部饭盒并返回饭堂的总时间（分钟）,结果保留2位小数。


Examples

Input Format

10 5
10 0 4 0 7
20 5
0  0 0 0 21
20 5
0  0 0 20 0

Output Format

185.25
205.25
85.00

Solution C++

#include <iostream>
#include <stdio.h>
using namespace std;
const int NN = 101;
const int MM = 101;

const double ROAD = 10;
const double RECEIVES = 15.0/60;

int FindNextBuilding(int rices[], int start)
{
    int i;
    for (i = start; i >=0; i--)
        if (rices[i] != 0)
            return i;
    return -1;
}


double Process(int rices[], const int M, const int N)
{
    double sum = 0;
    int send = 0;
    int i, j;

    i = N - 1;
    while ( (i = FindNextBuilding(rices, i)) != -1)
    {
        sum += (i+1) * ROAD * 2;
        send = 0;

        for (j = i; j >=0; j--)
        {
            if (send >= M)
            {
                break;
            }
            else if (rices[j] >= M - send)
            {
                rices[j] -= M - send;
                send = M;   
                break;
            }
            else
            {
                send +=  rices[j];
                rices[j] = 0;
            }            
        }

        i = j;
        
    }
    return sum;
}


int main()
{

    int M, N, i;
    int rices[NN];
    double dsum;
    while(cin>>M >>N)
    {
        dsum = 0;
        for (i = 0; i < N; i++)
        {
            scanf("%d", &rices[i]);

            dsum += rices[i] * RECEIVES;
        }

        dsum += Process(rices, M, N);
        printf("%.2f\n", dsum);
        //cout<<dsum <<endl;
    }

	return 0;
}

Solution Java

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	    Scanner in = new Scanner(System.in);
	    while(in.hasNextInt()){
	    	int M = in.nextInt();
	    	int N = in.nextInt();
	    	int a[] = new int[N];
	    	int sum = 0;
	    	for(int i = 0;i<N;i++){
	    		a[i] = in.nextInt();
	    		sum += a[i];
	    	}
	    	int t1 = sum*15;
	    	int t2 = 0;
	    	
	    	for(int i = N-1;i>=0;i--){
	    		boolean bl = false;
	    		int F = M;
	    		while(true){
	    		
		    		if(F==0){
		    			F=M;
		    			bl = false;
		    		}
		    		
		    		if(a[i]==0) break;
		    		
		    		t2 += (i+1)*20*60;
		    		
		    		for(int j = N-1;j>=0;j--){
		    			while(a[j]>0&&F>0){
		    				a[j]--;
		    				F--;
		    			}
		    			if(F==0){
		    				bl = true;
		    				break;
		    			}
		    			if(bl) break;
		    		}
		    	
	    	}
	    	}
	    	int res = t1 + t2;
	    	double result = res*1.0/60;
	    	System.out.printf("%.2f",result);
	    	System.out.println();
	    }
    }
}
请先登陆