Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) C.Producing Snow-白红宇

Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) C.Producing Snow

阅读量：7045 次

发布时间：2019-06-28

本文共 1000 字，大约阅读时间需要 3 分钟。

题意

每天有体积为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
              #include
               
                using namespace std;typedef long long LL;const int maxn = 1e5+5;const int mod = 77200211+233;typedef pair
                
                  pii;#define X first#define Y second#define pb push_back//#define mp make_pair#define ms(a,b) memset(a,b,sizeof(a))const int inf = 0x3f3f3f3f;#define lson l,m,2*rt#define rson m+1,r,2*rt+1priority_queue
                 
                   que;int V[maxn];int main(){ int n; scanf("%d",&n); for(int i=0;i
                  
                   = -(sumT+T) ){ ans -= que.top()+sumT; que.pop(); } sumT += T; ans += 1LL*T*que.size(); printf("%lld ",ans); } return 0;}

转载于:https://www.cnblogs.com/fht-litost/p/8707916.html

你可能感兴趣的文章