小可爬楼

时间限制：1秒        内存限制：128M

题目描述

小可在上一个题中，把A1这栋楼建的非常高，现在他在这栋楼里建了 n 阶台阶。

第1阶台阶比地面高 a1a​1​​ 厘米，第 i 阶台阶比前一阶台阶高 aia​i​​ 厘米。

现在小可由 q 次查询每次查询输入一个正整数 x ，表示小可的跳跃高度为 x 厘米，所以小可的跳跃高度x至少为 aia​i​​ 的时候，才能爬上第 i 阶台阶。

现在小可想知道，对于每次查询的 x，他最多可以距离地面多高。

输入描述

第一行：输入一个正整数 t ，表示多组输入的测试样例数。

对于每组数据：

第一行：输入两个正整数 n 和 q，表示楼梯的数量和查询次数。

第二行：输入 n 个正整数 aia​i​​ ，表示第 i 阶台阶比 i-1 阶台阶高多少。

第三行：输入 q 个整数，表示q次查询，每次输入为小可的跳跃高度。

输出描述

对于每组数据，输出一行 q 个整数，表示小可最多可以距离地面多高。

输入样例

1. 3
2. 4 5
3. 1 2 1 5
4. 1 2 4 9 10
5. 2 2
6. 1 1
7. 0 1
8. 3 1
9. 1000000000 1000000000 1000000000
10. 1000000000

输出样例

1. 1 4 4 9 9
2. 0 2
3. 3000000000

数据描述

25%的数据下：1≤t≤2,1≤n,q≤10^3,1≤ai≤1000

100%的数据下：1≤t≤100,1≤q,n≤2×10^5,0≤ai,xi≤10^9​​ 且多组输入的 n 的和不超过 2×1052×10​5​​ ,多组输入的 q 的和不超过 2×10^5

样例解释

样例1解释：如图，

如果小可跳跃高度为1，则只能爬 1级楼梯，所以他能爬到的最高高度是 1 厘米 。

如果小可跳跃高度为 2 或 4 ，那么他只能爬 1、 2和 3级楼梯，所以他能爬到的最高点是 1+2+1=4 厘米。

如果小可跳跃高度为 9 或 10，那么他可以爬上整个楼梯，所以他能爬到的最高处是1+2+1+5=9 厘米。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 2*1e5+5;
long long n,a[N],T,x,q,dp[N],r[N];
int main(){
// 	freopen("climbing.in","r",stdin);
// 	freopen("climbing.out","w",stdout);scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&q);memset(r,0,sizeof r);	memset(dp,0,sizeof dp);	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=n;i++) r[i]=r[i-1]+a[i];for(int i=1;i<=n;i++){dp[i]=max(dp[i-1],a[i]);}for(int i=1;i<=q;i++){scanf("%lld",&x);int pos;if(x>=dp[n]) {pos=n;goto A;	}for(int j=1;j<=n;j++){if(x<dp[j]){pos=j-1;goto A;	}}A: printf("%lld ",r[pos]);}printf("\n");}return 0;
}