牛客网 - [北京信息科技大学第十一届程序设计竞赛]andy的树被砍了(前缀和+二分)

题目链接：https://ac.nowcoder.com/acm/contest/940/J/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

andy又开始种树了，他觉得老用魔法不太好，这次他决定老老实实地每天种一棵树，第i天种一颗高度为hi的树，按理说老老实实种树就完事了，哪有那么多问题呢？但是他们学校有个叫kotori的人，非常爱砍树，每天都会把所有andy已经种下的树砍掉ci，如果第i天的时候某棵树的高度已经小于等于ci了，那么这棵树就会死亡，以后再也不会被砍了。并且如果到了第n天，有一些树还没被砍，那么kotori就会在第n + 1天把这些树全部砍死。

输入描述

第一行输入一个整数n，表示andy会种n天的树。
第二行含有n个数hi，表示andy在第i天种的树的高度为hi米。
第三行含有n个ci，表示kotori在第i天把所有andy已经种下的树砍掉ci。
1 <= n, hi, ci <= 1e5

输出描述

输出一行n个数di，每个数后面有一个空格(包括最后一个数)，最后需要换行。
表示andy第i天种的树会在第di天死亡，如果第n天这棵树还没有死亡，则输出n + 1。

输入

10
5 7 5 4 1 7 4 3 10 6 
6 4 2 4 1 8 5 7 3 5 

输出

1 4 4 4 5 6 7 8 11 11 

说明

第1天andy种的树高度为5，这天kotori要把andy已经种下的所有树砍掉6，所以第1棵树在第1天就死掉了。
第2天andy种的树高度为7，第2天被kotori砍掉了4，还剩3，第3天被kotori砍掉了2，还剩1。第4天被砍掉4，所以它在第4天死亡。
第10天andy种下的数高度为6，第10天被kotori砍掉了5，还剩1，也就是说它在第10天还没有死亡，所以它会在第11天被kotori砍死（参见题目描述最后一句）。

解题思路

题意:每天都要种树，每天也要砍树，求n棵树将在哪天被砍死。
思路:对位置i，应该找i~n+1中c[i]前缀和超过h[j]的最小位置。因此要求出c的前缀和c，二分查找c[j-1]=h[j]的最小位置。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long c[N], h[N];
int slove(int l, int r, long long k) {
    int mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (c[mid] >= k)
            r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &h[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
        c[i] += c[i - 1];
    }
    c[n + 1] = c[n] + N;
    for (int i = 1; i <= n; i++)
        printf("%d%c", slove(i, n + 1, c[i - 1] + h[i]), "\n "[i != n]);
    return 0;
}