14236: 【原4236】Tubes

题目

题目描述

author: Pikachu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4236

题目内容

小Z的同学要做许多实验，某个实验需要\(n\)个试管。她在第\(i\)个小时往第\(i\)个试管里面有\(V_i\)微升液体。而第\(j\)小时，每个试管都会蒸发\(R_j\)微升该液体直到试管全空。请问每一个小时所有试管总共蒸发了多少液体？

输入格式

第一行一个整数\(n\)。
第二行\(n\)个整数，代表\(n\)个试管中的液体体积\(V_i\)。
第三行\(n\)个整数，代表\(n\)个小时中蒸发液体体积\(R_j\)。

输出格式

输出一行\(n\)个整数，第\(i\)个整数代表第\(i\)个小时所有试管中蒸发的溶液总体积。

样例输入1

3
10 10 5
5 7 2

样例输出1

5 12 4

样例解释

第一个小时同学向试管1中加入了10ul的液体，同时要蒸发5ul，剩余3个试管的液体体积为5ul（-5ul），0ul，0ul。这一个小时蒸发了5ul。
第二个小时同学向试管2中加入了10ul的液体，每个试管要蒸发7ul，因此剩余3个试管的液体体积为0ul（-5ul，因为只剩下5ul。），3ul（-7ul），0ul。这一个小时蒸发了12ul。
第三个小时同学向试管3中加入了5ul的液体，每个试管要蒸发2ul，因此剩余3个试管的液体体积为0ul，1ul（-2ul），3ul（-2ul）。这一个小时蒸发了4ul。

温馨提醒

中间结果大概率会超过int，注意使用long long。

数据规模

对于100%的数据，\(1 \leq n \leq 10^5\)，\(0 \leq V_i \leq 10^9\)，\(0 \leq R_j \leq 10^9\)。

zqy2018's solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, v[100005], r[100005], cnt[100005] = {0};
ll sum[100005], res[100005] = {0};
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &v[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &r[i]), sum[i] = sum[i - 1] + 1ll * r[i];
    for (int i = 1; i <= n; ++i){
        int dd = upper_bound(sum + 1, sum + n + 1, sum[i - 1] + v[i]) - sum;
        cnt[i]++, cnt[dd]--;
        res[dd] += (1ll * v[i] - sum[dd - 1] + sum[i - 1]);
    }
    int ss = 0;
    for (int i = 1; i < n; ++i){
        ss += cnt[i];
        printf("%lld ", 1ll * ss * r[i] + res[i]);
    }
    ss += cnt[n];
    printf("%lld\n", 1ll * ss * r[n] + res[n]);
    return 0;
}