MuWu的卡牌游戏 | 前缀后缀

MuWu的卡牌游戏 | 前缀后缀

MuWu的卡牌游戏 | 前缀后缀

oj.cupacm.com

Time limit：1s

Memory limit：256MB

Problem Description

MuWu发明了一个卡牌游戏，他想邀请你一起玩，你这么好心应该不会拒绝他吧。

游戏的规则很简单：桌上有n张卡牌，第ii张卡牌上有一个整数值ai，MuWu指定一个数字x，你需要取前x张卡牌，其余的卡牌任意挑选，他想问你，你手上卡牌值的和最大为多少。

由于一轮游戏过于简单，MuWu想和你玩q轮游戏。

Input

第一行两个数n,q，代表有n张卡牌，q轮游戏。

第二行n个数，第i个数代表第i张卡牌上的整数值ai。

后面跟着q行，每一行有一个数x，你需要取前x张卡牌，其余卡牌任选。

1≤n≤2∗1051≤q≤2∗1051≤x≤n1≤ai≤104

Output

q行，每行代表一个问题的答案。

Sample Input

5 5-1 2 -3 4 -512345

Sample Output

5522-3

很容易看出来，题目就是求前x哥数的和，加上x之后的正数。

#includeusing namespace std;int x[200005],pre[200005],rear[200005];//原数组，前面选中的数的和，之后的正数之和int n,m,sum = 0;int main(){ scanf("%d %d",&n,&m); for(int i = 1;i <= n;++i) scanf("%d",&x[i]),pre[i] = pre[i - 1] + x[i]; for(int i = n;i>= 1;--i) if(x[i] > 0) sum += x[i],rear[i] = sum; else rear[i] = sum; while(m--){ scanf("%d",&sum); printf("%d\n",pre[sum] + rear[sum + 1]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。