题目链接:http://acm.zzuli.edu.cn/problem.php?id=2198
时间限制: 1 Sec  内存限制: 128 MB

题目描述

在ICPC程序设计大赛期间，小P作为志愿者的任务是给各个学校送盒饭，小P一次最多可以携带M份盒饭。总共有N个学校来参加比赛，这N个学校的休息点在一条笔直的马路边一字排开，路的一头是小P取盒饭的地方，假设为原点，每两个相邻点之间，小明需要行走15秒，包括从原点到第一个休息点，交付一份盒饭需要3秒时间。从第一个休息点到第N个休息点需要的盒饭数分别为 a1, a2, a3..., an。 问小P最短需要多少时间把全部盒饭送完并回到原点。 

输入

第一行输入一个正整数T，表示有T组测试数据，每组占两行，第一行两个整数M、N（0<M，N<50），第二行输入N个整数a1  a2  a3 ...an （0<=a1....an<50） 

输出

每行输出一个整数，对应一组测试数据，表示小P送完全部盒饭并返回原点的总时间（秒）。  

样例输入

2
18 2
8 6
10 3
5 0 8

样例输出

102
159

提示

消耗的时间最少只由走的路程最短决定，每一趟来回走的路程是这一次送餐的最远的点距离原点的两倍。

解题思路

我们可以先送后面的，把后面的送过了，再往前送，一直这样模拟就行了。。。

#include <stdio.h>
int main() {
    int m, l, c, t, mz, ans, a[55];
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &m, &l);
        for (int i = 1; i <= l; i++)
            scanf("%d", a + i);
        mz = m;
        while (!a[l] && l)
            l--;
        ans = 15 * l;
        while (l > 0) {
            ans += a[l] * 3;
            if (a[l] > m) {
                a[l] -= m;
                m = mz;
                c = a[l] / m;
                ans += (l * 15 * 2) * (c + 1);
                if (a[l] % mz) {
                    m -= a[l] % mz;
                    a[l] = 0;
                }
                else {
                    a[l] = 0;
                    ans -= l * 15;
                    while (!a[l] && l)
                        l--;
                    m = mz;
                    ans += l * 15;
                }
            }
            else {
                m -= a[l];
                a[l] = 0;
                while (!a[l] && l) {
                    l--;
                    ans += 15;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}