补题：2018HUD暑期多校训练第八场-From ICPC to ACM（hdu-6408）（贪心+数据结构）

题目链接：
hdu-6408

题目大意：
给你k个月，告诉你每个月原材料的价格，用户需求量，组装电脑价格，公司最大产量
以及从本月到下一个月，电脑可存放量，原材料存放价格，电脑存放价格
求k个月下来，公司是否可以满足用户需求，如果可以输出最小成本，否则输出-1

解题思路：
由题目可知，原材料的存储量是无限的，那么我们是否可以贪心的使用原材料价格最小的去组装电脑（当然这里需要考虑上存放原材料的钱，使用需要动态更新最小值）。
对于电脑来说，我们可以用一个multiset来维护，先假设公司每个月都最大量生产，存入multiset,然后按照成本从小到大排序，每个月把成本最小的卖掉，进入下个月时，如果存放不了这么多电脑，则把成本高的丢弃，这样就可以达到成本最小了。

小编暴力模拟，发现时间要很高，所以需要配合pair来一起维护电脑，第一个存放电脑的成本，第一个存放该成本电脑的数量。
为了后面方便计算以及更新电脑成本小的，我们可以设置一个偏移量sumE,插入时减去这个偏移量，需要用该成本电脑时加上此时的偏移量，类似前缀和的效果，则可快速实现该过程。

AC代码如下：

#include <bits/stdc++.h>

using namespace std;


long long c[100007],d[100007],m[100007],p[100007];
long long e[150050],R[150050],E[150050];

void init(){
    memset(e,0,sizeof(e));
    memset(R,0,sizeof(R));
    memset(E,0,sizeof(E));
}

int main()
{
   freopen("l.in","r+",stdin);
    long long t;
    scanf("%lld",&t);
    while(t--){
     //   init();
        long long k;
        scanf("%lld",&k);
        for(long long i=1; i<=k; ++i){
            scanf("%lld%lld%lld%lld",&c[i],&d[i],&m[i],&p[i]);
        }

        E[0] = e[0] = R[0] = 0;
        for(long long i=1; i<k; ++i){
            scanf("%lld%lld%lld",&e[i],&R[i],&E[i]);
        }

        long long _month = 1, flag = 0;
        long long sumE = 0;
        long long minRcost = c[1];
        long long ans = 0;
        long long totnum = 0;
        multiset<pair<int,int>> cpt;

        while(_month<=k){
            minRcost = min(minRcost,c[_month]);

           if(totnum + p[_month] < d[_month]){
               flag=1;
               break;
           }
            totnum += p[_month];
            cpt.insert(make_pair(m[_month]-sumE+minRcost,p[_month]));
            multiset<pair<int ,int>>::iterator pos;
            totnum -= d[_month];
            while(d[_month] && !cpt.empty()){
                pos = cpt.begin();
                pair<int,int> temp = *pos;
                int num = temp.second;
                int mon = temp.first;

                if(num <= d[_month]){
                    d[_month]-=num;
                    ans = ans + (mon+sumE)*num;
                    cpt.erase(pos);
                }else{
                    num-=d[_month];
                    ans = ans + (mon+sumE)*d[_month];
                    cpt.erase(pos);
                    cpt.insert(make_pair(mon,num));
                    d[_month] = 0;
                }
            }

            while(totnum > e[_month]){
                pos = cpt.end(); pos--;
                pair<int,int> temp = *pos;
                cpt.erase(pos);
                if(totnum - temp.second < e[_month]){
                    temp.second -= (totnum - e[_month]);
                    cpt.insert(make_pair(temp.first, temp.second));
                    totnum = e[_month];
                }else{
                    totnum -= temp.second;
                }
            }

            if(d[_month]){
                flag=1;
                break;
            }
            if(_month<k){               
                minRcost += R[_month];
                sumE += E[_month];
            }
            _month++;
        }

        if(flag) printf("-1\n");
        else printf("%lld\n",ans);
    }
    return 0;
}