2664 - 雨中外卖

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

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

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

Input

有多组测试用例，

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

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

Output

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

Examples

Input

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

Output

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;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题