Codeforces Round #478 (Div. 2)---C. Valhalla Siege(1400+二分+前缀和)

简介: 算法

C. Valhalla Siege

26.png

题意:有n个勇士一排排好,有血量,然后会有q次进攻,每次进攻都会扣勇士qi点血,如果勇士死了自动杀下一个,全死了将会在下一轮之前复活,要求输出每次进攻完之后剩了几个勇士

思路:二分加前缀和处理

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=200008;
int a[maxn],sum[maxn];
signed main()
{
  int n,i,j,t,k,q;
  cin>>n>>q;
  for(i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  for(i=1;i<=n;i++)
  {
    sum[i]=sum[i-1]+a[i];
  }
  int sum1=0;
  for(i=1;i<=q;i++)
  {
    int cx;
    cin>>cx;
    sum1+=cx;
    if(sum1>=sum[n])
    {
      cout<<n<<endl;
      sum1=0;
      continue;
    }
    int l=1,r=n+1;
    while(r-l>1)
    {
      int mid=l+r>>1;
      if(sum[mid]>sum1)
      {
        r=mid;
      }
      else 
      {
        l=mid;
      }
    }
    if(sum1<a[l])
      cout<<n-l+1<<endl;
    else 
      cout<<n-l<<endl;
  }
}
// 1 3   6  10
// 9 10 20  26
// 9 0  0   6
相关文章
|
6月前
|
机器学习/深度学习 人工智能 BI
The Great Hero(Codeforces Round #700 (Div. 2))模拟+贪心思想和排序
The Great Hero(Codeforces Round #700 (Div. 2))模拟+贪心思想和排序
64 0
Codeforces Round 859 (Div. 4)题解
Codeforces Round 859 (Div. 4)题解
106 0
【算法题解】Codeforces Round #817 (Div. 4)题解
【算法题解】Codeforces Round #817 (Div. 4)题解
【算法题解】Codeforces Round #817 (Div. 4)题解
|
人工智能 BI
Codeforces Round #805 (Div. 3) 题解
Codeforces Round #805 (Div. 3) 题解
Codeforces Round #805 (Div. 3) 题解
|
人工智能 索引
Codeforces Round #806 (Div. 4) 题解
Codeforces Round #806 (Div. 4) 题解