题目链接

题意

每天有体积为Vi的一堆雪，所有存在的雪每天都会融化Ti体积，求出每天具体融化的雪的体积数。

分析

对于第i天的雪堆，不妨假设其从一开始就存在，那么它的初始体积就为V[i]+T[1..i-1]，在第i天则需要融化T[i]体积，若T[1….i]>=V[i]+T[1…i-1]，那么这堆雪就融化完了，融化的体积为V[i]+T[1..i-1] - T[1…i-1]；否则就为T[i]。用个优先队列来维护，由于默认是数值大的优先，所以实际处理中添加一个负号。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

priority_queue que;
int V[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=;i= -(sumT+T) ){
ans -= que.top()+sumT;
que.pop();
}
sumT += T;
ans += 1LL*T*que.size();
printf("%lld ",ans);
}
return ;
}