codeforces 975C Valhalla Siege

时间:2023-03-08 20:39:42

题意:

有n个巫师站成一列,每个巫师有自己的血量。

一个人射箭攻击他们,每次造成若干点伤害,巫师按照给定的顺序承受伤害,如果伤害大了,那么死掉,伤害落到下一个巫师身上。

如果一轮攻击之后,所有的巫师都死了,那么他们会立即复活。

给出若干个询问,问每轮攻击之后还剩多少巫师活着。

思路:

前缀和加二分,每次伤害累加,大于了总和便归零且复活。

代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 2e5 + ;
long long pre[N],a[N];
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for (int i = ;i < n;i++)
{
scanf("%lld",&a[i]);
}
pre[] = a[];
for (int i = ;i < n;i++) pre[i] = a[i] + pre[i-];
long long ans = ;
for (int i = ;i < q;i++)
{
long long b;
scanf("%lld",&b);
ans += b;
if (ans >= pre[n-])
{
printf("%d\n",n);
ans = ;
}
else
{
int pos = lower_bound(pre,pre+n,ans) - pre;
long long gg = pre[pos];
int tt = ;
if (gg == ans)
{
tt = n - pos - ;
}
else
{
tt = n - pos;
}
printf("%d\n",tt);
}
}
return ;
}