CodeForces

博客界面的小人搞不好导致无心写博客

题意：tyd非常喜欢玩雪，下雪下了n天，第i天她会堆一堆大小为Vi的雪堆，但因为天气原因，每堆雪会融化Ti，问每天总共融化了多少雪；

直接上代码＋注释

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<iostream>
#define ll long long
using namespace std;

ll a[100100],b[100100],c[1010000],sum[100100],d[100100],e[101000];

int ef(int mid,int i)
{
    if(a[i]>c[mid]-c[i-1]) return 1;
    return 0;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    for(int i=0;i<n;i++){
        scanf("%lld",&b[i]);
        c[0]=b[0];
        if(i) c[i]=c[i-1]+b[i];
    }
    for(int i=0;i<n;i++){
        ll l=i,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(ef(mid,i)) l=mid+1;          ///二分找到可以完全融化b[i]的最后一堆；
            else r=mid;
        }
        d[i]++;d[l]--;                      ///他可以坚持的最后那一堆--； 第1堆++；
        sum[l]+=(a[i]-c[l-1]+c[i-1]);       ///把多（少）的那部分（最后一堆）存在一个数组里
    }                                       ///如果是少的话就是负数加进去
    for(int i=0;i<n;i++)
        e[i]=e[i-1]+d[i];                   ///统计每次有多少堆（多的或少的都在sum数组里）,每次++只是最开始那堆 所以加起来 多加的部分在l堆就--了；
    for(int i=0;i<n;i++)
        printf("%lld ",e[i]*b[i]+sum[i]);   ///堆数*每次融化量+多（少）的那部分
    printf("
");
    return 0;
}