中文题目:工作安排

原文题目：Work Scheduling

本题可以采用贪心

算法一：按工作时间排序，如果工作能按时完成的工作就按时完成，如果工作不能按时完成就把之前价值最小的工作和当前作比较，取最优的情况。考虑使用堆维护工作价值。

算法二：按工作价值排序，因为所有工作花费的是一样的，价值大的尽量完成，考虑把工作拖到最后完成。每个工作从完成期限往前找，找到第一个空的时段，用这个时间完成工作。考虑用并查集快速查找空的时段。如果该工作完成时间>n，则一定可以完成，并查集只要维护<=n的部分。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define LL long long  5 struct Work{
    int d,p;}W[100005]; 6 std::priority_queue
         
          
           ,std::greater
           
             >Q; 7 bool cmp(Work A,Work B){ return A.d
           
          
         
        
       
      

#include 
       
        #include 
        
         #define LL long long int Pre[100005];struct Work{
     int d,p;}W[100005];bool cmp(Work A,Work B){
     return A.p>B.p;}int GetPre(int x){
     return Pre[x]==x?x:Pre[x]=GetPre(Pre[x]);}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    int n;LL ans=0;    scanf("%d",&n);    for(int i=1;i<=n;++i)        scanf("%d %d",&W[i].d,&W[i].p);    std::sort(W+1,W+n+1,cmp);    for(int i=1;i<=n;++i)Pre[i]=i;    for(int i=1,pre;i<=n;++i)        if(W[i].d>n){            ans=ans+W[i].p;        }else{            pre=GetPre(W[i].d);            if(!pre)continue;            ans=ans+W[i].p;            Pre[pre]=pre-1;        }    printf("%lld",ans);    //fclose(stdin);fclose(stdout);    return 0;}