贪心搭台，标签思想唱戏！

· · 题解

题目大意

公司里有多种员工，每种员工数量已知。现在有若干个工程待完成，完成每项工程都对各类员工的数目有一定最低要求，且完成每项工程后都会获得一定数目新员工的奖励。求能完成的最多工程数。

题目分析

由于员工不是消耗品,显然越多越好，且获得员工的时机并不影响以后工程的完成，因此该问题显然满足无后效性。那么贪心算法就已经呼之欲出了！我们只要不停的遍历所有工程，遇到可完成的就直接完成并累加员工数，当任何工程都无法完成时，则输出已完成的工程数，最终的时间复杂度为 n^3 。面对十的五次方规模的数据，显然难以忍受。接下来考虑优化！

解法优化

标签思想是 OI 界的重要思想之一，本题更是体现的淋漓尽致。观察到保证 m_i 与 k_i 之和均不超过 10^5，我们应当以此为着手点进行代码迭代，发力数据规模痛点，对题目需求进行归因分析，从而打出一套组合拳，完成对此题目的降维打击！

具体而言，我们为每一个员工类型开一个标签，数组用于维护这些标签，标签中则存储所有对该类员工有需求的工程序号与需求数量。当该类员工数值有所更新时，在维护得到已达到的为需求数目。此外，我们还需要一个计数数组来记录每个工程的待满足需求数，当待满足要求数为零时，说明该工程已可实施，则可将其放入一个栈或队列中，从而通过维护这个栈或队列来统计答案。注意到 1 \le t_i, u_i \le 10^9，我们难以开如此巨大的数组，所以考虑离散化或 unorder_map。 最终复杂度为 O(n)，采用离散化的话则是 O(n \log n)，其他具体的实现细节可以移步代码实现，里边的注释还是挺详细的！

代码实现

#include<bits/stdc++.h>
using namespace std;
struct tagy{
    int gongcid,wnum;
    bool operator < (const tagy &x) const {
        return (wnum==x.wnum) ? gongcid<x.gongcid : wnum<x.wnum;
    }//注意这里的小于号重载
    tagy(int G,int W){
        gongcid=G,wnum=W;
    }
};
//构建一个标签结构体，分别记录各个工程序号及需求员工数量。
struct rwd{
    int kd,nm;
    rwd(int K,int N){
        kd=K,nm=N;
    }
};
//构建一个奖励结构体，用于在处理可实施工程时候更新员工数量。
int n,m,tn1,tn2,ans;
int cnt[500005];//记录每个工程的待满足需求量
unordered_map<int,int> ar; //记录每种员工目前的数量
stack<int> s;//维护目前可实施的全部工程
map<int,set<tagy> > tgm; 
vector<rwd> v[500005];
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&tn1,&tn2);
        ar[tn1]=tn2;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&n);
        int t=0;
        while(n--){
            scanf("%d%d",&tn1,&tn2);
            if(ar[tn1]>=tn2) continue; //若已满足，则忽略。
            tgm[tn1].insert(tagy(i,tn2));
            t++;
        }
        if(!t) s.push(i);
        cnt[i]=t;
        scanf("%d",&n);
        while(n--){
            scanf("%d%d",&tn1,&tn2);
            v[i].push_back(rwd(tn1,tn2));
        }
    }
    while(s.size()){
        ans++; n=s.top(); s.pop();
        for(int i=0;i<v[n].size();i++){
            ar[v[n][i].kd]+=v[n][i].nm;
            while(1){
                if(tgm[v[n][i].kd].size()==0) break; 
                set<tagy>::iterator IT;
                IT=tgm[v[n][i].kd].begin();
                if((IT->wnum) > ar[v[n][i].kd]) break;
                cnt[IT->gongcid]--;
                if(cnt[IT->gongcid]==0) s.push(IT->gongcid);
                tgm[v[n][i].kd].erase(IT);
            }
        }
    }
    cout<<ans;
    return 0;
}

需要注意的是，本参考代码使用了 unordered_map，因此需要 C++11 及以上版本。

（PS.记得雁过留声啊）