[codeforce 975C] Valhalla Siege （二分）

Examples

input

5 5

1 2 1 2 1

3 10 1 1 1

output

3

5

4

4

3

input

4 4

1 2 3 4

9 1 10 6

output

1

4

4

1

Note

In the first example:

after the 1-st minute, the 1-st and 2-nd warriors die.

after the 2-nd minute all warriors die (and all arrows left over are wasted), then they will be revived thus answer is 5 — all warriors are alive.

after the 3-rd minute, the 1-st warrior dies.

after the 4-th minute, the 2-nd warrior takes a hit and his strength decreases by 1.

after the 5-th minute, the 2-nd warrior dies.

题目大意：

有一列n个勇士，承受q分钟的箭击，第i个人承受值为a[i]，第i分钟会有攻击值为k[i]的箭击，当第i个人受到a[i]的箭击后将死亡（倒下），该分钟剩余的攻击或下一分钟的攻击将会作用于死亡人后面的人身上，当某分钟所有人均死亡时，将会在该分钟满血复活，该分钟剩余的攻击值无效，即该分钟后所有人满血站着（由第二个样例可知复活可触发无限次）

现在给出n,q,a[i],k[i]输出每分钟结束后还站着的人数

先对a数组求前缀和

对每个k二分，寻找到第一个能承受住的人（或恰好go die的人）

记录last表示二分到的人受到攻击后剩余血量

sum表示从最近一次全体满血到现在为止箭击的总攻击量

注意各种情况即可

code：(cf比赛赶时间打的比较丑，懒得改了)

//Menteur_Hxy

#include <cstdio>

#include <iostream>

#include <algorithm>

#define ll long long

#define f(i,a,b) for(register int i=a;i<=b;i++)

using namespace std;

inline ll rd() {

    ll x=0,fla=1; char c=' ';

    while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();}

    while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();

    return x*fla;

}

inline void out(ll x){

    int a[25],wei=0;

    if(x<0) putchar('-'),x=-x;

    for(;x;x/=10) a[++wei]=x%10;

    if(wei==0){ puts("0"); return;}

    for(int j=wei;j>=1;--j) putchar('0'+a[j]);

    putchar('\n');

}

const int MAX=2000100;

int n,q;

ll a[MAX],k[MAX];

int main() {

    n=rd(),q=rd();

    f(i,1,n) a[i]=rd()+a[i-1];

    ll sum=0,l=1,r=n,last=0;

    f(i,1,q) {

        ll k=rd();

        if(k >= a[n]-sum) {

            out(n);

            sum=0,l=1,r=n,last=0;

            continue;

        }

        while(l<r) {

            int mid=(l+r)>>1;

            if(a[mid]-sum >= k) r=mid;

            else l=mid+1;

        }

        sum+=k;r=n;

        last=a[l]-sum;

        // cout<<l<<" "<<r<<" "<<sum<<" "<<last<<" "<<las<<" ";

        out(last==0?n-l:n-l+1);

        if(!last) l++;

    }

    return 0;

}

巴特西

[codeforce 975C] Valhalla Siege （二分）

题目大意：

最新文章

热门文章