题目描述

一共有 n 个箱子排成一排，从左到右依次编号为 1∼n。

其中，第 i 号箱子中放有 ai 个石子。

现在，你可以进行最多 d 次操作。

每次操作可以将一个石子从一个箱子移动至另一个与其相邻的箱子里。

我们希望通过合理操作使得 1 号箱子内的石子数量尽可能大。

请问，这个最大可能值是多少？

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 n 和 d。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
每组数据输出一行结果，表示答案。

数据范围
1≤T≤100,
1≤n,d≤100,
0≤ai≤100

样例

输入样例：
3
4 5
1 0 3 2
2 2
100 1
1 8
0
输出样例：
3
101
0

算法1

(遍历) $O(n)$

1.c从左往右遍历

2.右边的移动到最左边，是有距离成本的。
要 乘以距离

时间复杂度

参考文献

python3 代码

T = int(input())
for _ in range(T):
    n, d = map(int, input().split())
    a = [int(x) for x in input().split()]

    res = a[0]
    for i in range(1, n):
        dist = i        #要移动的距离
        if d > 0:       #还可以移动
            cur = min(d // dist, a[i])
            res += cur
            d -= cur * dist
        else:
            break
    print(res)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int T;    cin >> T;
    while (T --)
    {
        int n;    cin >> n;
        int d;    cin >> d;
        int a[n];
        for (int i = 0; i < n; i ++)
            cin >> a[i];

        int res = a[0];
        for (int i = 1; i < n; i ++)
        {
            if (d > 0)
            {
                int dist = i;
                int cur = min(d / dist, a[i]);
                res += cur;
                d -= cur * dist;
            }
            else
            {
                break;
            }
        }
        cout << res << endl;
    }

    return 0;
}

java 代码

import java.util.* ;

public class Main
{
    public static void main(String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T -- > 0)
        {
            int n = scan.nextInt();
            int d = scan.nextInt();
            int [] a = new int [n];
            for (int i = 0; i < n; i ++)
                a[i] = scan.nextInt();

            int res = a[0];
            for (int i = 1; i < n; i ++)
            {
                if (d > 0)
                {
                    int dist = i;
                    int cur = Math.min(d / dist, a[i]);
                    res += cur;
                    d -= cur * dist;
                }
                else
                {
                    break;
                }
            }

            System.out.println(res);
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla