16510번 Predictable Queue

충남대학교 제 2회 생각하는 프로그래밍 대회 H번 문제

이분 탐색 문제이다.

관련 유형의 문제들을 안 풀다보니, 감각을 조금 잃어버린 것 같다.

비슷한 문제들을 풀어봐야겠다.

https://www.acmicpc.net/problem/16510

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
vector<long long> v;
 
int bs(int left, int right, long long s)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;
 
        if (s < v.at(middle))
        {
            right = middle - 1;
        }
        else if (s > v.at(middle))
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }
 
    return right;
}
 
int main(void)
{
    int N = 0, M = 0;
    long long input = 0, sum = 0;    
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &input);
 
        sum += input;
 
        v.push_back(sum);
    }
 
    int s = v.size();
 
    for (int i = 0; i < M; i++)
    {
        scanf("%lld", &input);
 
        printf("%d\n", bs(0, s - 1, input) + 1);
    }
 
    return 0;
}