当前位置: 代码迷 >> 综合 >> 【Codeforces】Valhalla Siege(前缀和、二分)
  详细解决方案

【Codeforces】Valhalla Siege(前缀和、二分)

热度:64   发布时间:2024-01-28 10:50:46.0

思路:

怎么说呢,初入二分与前缀和的门槛(小小的眼睛,大大的疑惑)。

遇到这道题发现需要记录上次射出来的弓箭个数杀到哪一个人,这不就是明摆着说用二分、用二分吗(我丢)。但是二分必须要有顺序,哟呵,提醒我搞前缀和。(仔细一考虑,我好像略知皮毛,啥也不会、啥也不是....)最终看了看题解,搞了半天。

AC:

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2*1e5;
ll a[maxn],sum[maxn];
int main()
{int n,q;cin >> n >> q;for(int i = 1;i<=n;i++){cin >> a[i];sum[i] = sum[i-1]+a[i];//前缀和 }int beginn = 1;//表示现在活着的人在beginn这里 ll res = 0;while(q--){ll x;cin >> x;res+=x;int pos = upper_bound(sum+beginn,sum+n+1,res)-sum;//表示的是位置表示的找到第一个大于它的数字表示这个数字还是活着的if(pos == n+1){cout << n << endl;beginn = 1; res = 0;}else {beginn = pos; cout << n-pos+1 << endl;} }return 0;
}