CF978C Letters 문제 풀이 2 점

제목 링크:http://codeforces.com/problemset/problem/978/C
제목 설명 (인명, 지명 약간 개편)
학교 안 에는 침실 이 하나 있 는데, 침실 의 번 호 는 \ (1 \) 에서 \ (n \) 까지 이다.방 번호총 총 이 는 최근 에 학교 안의 이 구역 의 우 체 부 로 일 했다.그러나 그 를 곤 혹 스 럽 게 하 는 것 은 학교 학생 들 이 수령 주 소 를 작성 할 때 다른 주소 표기 방식 을 채택 했다 는 점 이다.그들 이 작성 한 수령 주 소 는 숫자 이지 만 이 숫자 는 어느 침실 의 어느 방 인지 직접 표시 할 수 없다.주소 의 번 호 는 \ (1 \) 부터 \ (a 1 + a 2 + \ cdots + a n \) 까지 입 니 다.그 중:

제 \ (1 \) 호 침실 건물의 제 \ (i \) 개 방 의 수신 주소 에 대응 하 는 번 호 는 \ (i \) 이다.

제 \ (2 \) 호 침실 건물의 제 \ (i \) 개 방 의 수신 주소 에 대응 하 는 번 호 는 \ (a 1 + i \) 이다.

제 \ (3 \) 호 침실 건물의 제 \ (i \) 개 방 의 수신 주소 에 대응 하 는 번 호 는 \ (a 1 + a 2 + i \) 이다.

…………

이렇게 유추 해 보면 마지막 오 피 스 텔 (즉 제 \ (n \) 호 오 피 스 텔) 의 마지막 방 (즉 제 \ (a n \) 개 방) 에 해당 하 는 번 호 는 다음 과 같다.
\(a_1 + a_2 + \cdots + a_n\)
오늘 은 총 총 이 가 소 포 를 배부 해 야 하 는데 이 소 포 를 받 을 주소 만 알 고 있 습 니 다. 각각 \ (b 1 \), \ (b 2 \),.........................................하지만 그 는 어떤 소포 에 대응 하 는 건물 번호 와 방 번 호 를 모 르 니 계산 해 주세요.
입력 형식
입력 한 첫 줄 에는 두 개의 정수 가 포함 되 어 있 습 니 다.(\ (1 \ \ le n, m \ le 2 \ times 10 ^ 5 \) 두 번 째 줄 은 \ (n \) 개의 정수 로 구 성 된 정수 서열 을 포함 합 니 다 \ (a 1, a 2, \ cdots, a n \) (\ (1 \ le ai \ \ \ le 10 ^ {10} \) 빈 칸 으로 구분 합 니 다.세 번 째 줄 은 \ (m \) 개의 정수 로 구 성 된 정수 서열 을 포함 합 니 다 \ (b 1, b 2, \ cdots, b m \) (\ (1 \ le bj \ le a 1 + a 2 + \ cdots + a n \) 빈 칸 으로 구분 합 니 다. 그 중 \ (b j \) 는 제 \ (j \) 개의 소포 에 대응 하 는 수령 주 소 를 표시 합 니 다.제목 은 모든 것 을 보증 합 니 다.
출력 형식
출력 줄각 줄 에는 두 개의 정수 가 포함 되 어 있 으 며, 하나의 빈 칸 으로 구분 되 어 있 으 며, 각각 이 소포 가 있 는 침실 의 건물 번호 \ (f \) (\ (1 \ le f \ le n \) 와 방 번호 \ (k \) (\ (1 \ le k \ \ le a f \) 를 나타 낸다.
제목 분석
이 문제 와 관련 된 알고리즘: 2 점.우선 2 점 이 필요 하 다 면 우 리 는 단조 로 운 배열 을 실현 해 야 한다.구 해 \ (sum [i] \) 도 간단 합 니 다. for 순환 을 엽 니 다. \ (sum [i] = sum [i - 1] + a [i] \)그리고 각각 에 대해 서 는 2 분 (sum \) 을 통 해 어느 침실 에 있 는 지 구 할 수 있 습 니 다.그리고 \ (b j \) 에 게 우 리 는 그의 침실 번 호 를 찾 았 다 \ (f \). 그러면 그의 방 번 호 는 \ (b j - a [f - 1] \) 이다.구현 코드 는 다음 과 같 습 니 다:

#include 
using namespace std;
const int maxn = 200020;
int n, m;
long long a[maxn], b, sum[maxn];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }
    while (m --) {
        cin >> b;
        int f = lower_bound(sum+1, sum+1+n, b) - sum;
        long long k = b - sum[f-1];
        cout << f << " " << k << endl;
    }
    return 0;
}