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

谁践踏了优雅 2022-05-16 09:16 74阅读 0赞

题目链接：  
[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;
    }

[hdu-6408]: http://acm.hdu.edu.cn/showproblem.php?pid=6408