CF948C Producing Snow 前缀和+二分

题目

Alice likes snow a lot! Unfortunately, this year’s winter is already over, and she can’t expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amount of snow every day. On day i he will make a pile of snow of volume $V_i$ and put it in her garden.

Each day, every pile will shrink a little due to melting. More precisely, when the temperature on a given day is $T_i$, each pile will reduce its volume by $T_i$. If this would reduce the volume of a pile to or below zero, it disappears forever. All snow piles are independent of each other.

Note that the pile made on day i already loses part of its volume on the same day. In an extreme case, this may mean that there are no piles left at the end of a particular day.

You are given the initial pile sizes and the temperature on each day. Determine the total volume of snow melted on each day.

$N \leq 10^9,V_i \leq 10^9 ,T_i \leq10^9$

Output a single line with N integers, where the i-th integer represents the total volume of snow melted on day i.

每天堆一个雪人,如果当天温度为T,那么所有存在的雪人体积减少$min(T,V_{remain})$,问每一天融化的雪的体积数.

in:                                       out:
3                               		  5 12 4
10 10 5                         
5 7 2

题解

我们很自然有这样一个思路,考虑每个雪人能完整的撑过哪几天,然后再加上那个不完整的那天.

每天融化的雪量= k*$V_i$+$extra_i$

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+7;
long long tag[MAXN];
long long  extra[MAXN];
long long  V[MAXN],T[MAXN];
long long sum[MAXN];
int main(){
	int N;cin>>N;
	for(int i=1;i<=N;++i){
		cin>>V[i];
	}
	for(int i=1;i<=N;++i){
		cin>>T[i];
		sum[i]=sum[i-1]+T[i];
	}

	for(int i=1;i<=N;++i){
		int t=V[i];
		int id=upper_bound(sum+1,sum+N+1,t+sum[i-1])-sum;
		tag[i]++;tag[id]--;
		extra[id]+=t-(sum[id-1]-sum[i-1]);
	}

	for(int i=1;i<=N;++i){
		tag[i]+=tag[i-1];
		cout<<tag[i]*T[i]+extra[i]<<" ";
	}
	return 0;
}