题目描述

一共有 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

C++ 代码

贪心解法

#include<iostream>
using namespace std;
const int N=110;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--) // t组测试数据
    {
        int n,d;
        cin>>n>>d;
        for(int i=1;i<=n;i++) cin>>a[i]; // 输入石子数量
        int res=a[1]; // 定义答案
        for(int i=2;d && i<=n;i++) // 如果有移动次数
        {
            while(a[i] && d) // 如果可以从第i个箱子移动石子
            {
                a[i]--; // 箱子石子数量减少
                d-=i-1; // 移动次数减少从i移动到1共i-1步
                if(d>=0) res++; // 如果可以移动到1号箱子
            }
        }
        cout<<res<<endl; // 输出最多的石子数量
    }
    return 0;
}