首页 > 代码库 > HDU4846Task treap + 贪心

HDU4846Task treap + 贪心

2024-07-14 18:28:16   220人阅读

题意：给你 n台机器，m个任务，机器有两个属性值  一天最多工作时间X，机器等级 Y  ，任务有两个属性值   需要机器的工作时间X，需要机器的工作等级 Y ，每台机器一天只能做一个任务，每做一个任务可以获得  500×Y + 2×X 的价值，问你在完成最多任务的情况下最多价值为多少。

解题思路：

首先是贪心，可以知道Y的影响比X大的多。所以对任务Y从大到大排序，然后在找最接近的机器，（从大到小填一定是最优的。）

解题代码：

  1 // File Name: 1004.cpp  2 // Author: darkdream  3 // Created Time: 2014年07月29日 星期二 09时51分07秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24  25 using namespace std; 26 #define LL long long  27 int fm; 28 int ok; 29 const int inf = ~0U>>1; 30 class treap 31 { 32    struct node{ 33        int value , key ,num; 34        node (int v, node *n):value(v) 35        { 36          c[0] = c[1] = n ;num = 1 ;  key = rand()-1; 37        } 38        node *c[2]; 39    }*root ,*null; 40    void rot(node *&t , bool d) 41    { 42       node *c = t->c[d]; 43       t->c[d] = c->c[!d]; 44       c->c[!d] = t;  45       t = c;  46    } 47    void insert(node *&t ,int x) 48    { 49      if(t == null) 50      { 51         t= new node(x,null); 52         return ; 53      } 54      if(x == t->value){ 55         t->num ++ ;  56         return ; 57      } 58      bool d = x > t->value; 59      insert(t->c[d],x);     60      if(t->c[d]->key < t->key) 61          rot(t,d); 62    } 63    void Delete(node *&t ,int x) 64    { 65        if(t == null) 66        { 67         ok = 0 ;  68         return ;  69        } 70        if(t->value =http://www.mamicode.com/= x && t->num != 1) 71        { 72           //printf("2*****"); 73           t->num -- ;  74           return ;  75        } 76        if(t->value  =http://www.mamicode.com/= x) 77        { 78          // printf("1*****"); 79           bool d = t->c[1]->key < t->c[0]->key; 80           if(t->c[d] == null) 81           { 82             delete t;  83             t = null ;  84             return ;  85           } 86           rot(t,d); 87           Delete(t->c[!d],x); 88        }else{ 89          bool d  = x > t->value;  90          Delete(t->c[d],x); 91        } 92    } 93    void find(node *t , int x) 94    { 95         if(t == null) 96             return ; 97        // printf("%d**\n",t->value); 98         if(t->value >= x) 99         {100               ok = 1; 101             fm = min(fm,t->value);102             find(t->c[0],x);103         }else{104             find(t->c[1],x);105         }106    }107    void Free(node *t)108    {109        if(t == null)110            return ;;111        if(t->c[1] != null)112            Free(t->c[1]);113        if(t->c[0] != null)114            Free(t->c[0]);115        delete t ;116        t = null;117    }118     public:119        treap()120        {121           null = new node(0,0);122           null->num = 0 ; 123           null->key = inf;124           root = null;125        }126        void ins(int x)127        {128           insert(root,x);129        }130        void del(int x)131        {132           Delete(root ,x);133        }134        void   f(int x)135        {136            find(root,x);137        }138        void fre()139        {140           Free(root);141        }142 143 };144 struct node1{145   int x, y ; 146 }K[100005];147 bool cmp(node1 x, node1 y)148 {149     if(x.x == y.x)150        return x.y > y.y;151     return x.x > y.x ; 152 }153 int main(){154    int n , m; 155    while(scanf("%d %d",&n,&m) != EOF)156    {157         treap T[104];158         for(int i =1 ;i <= n;i ++)159         {160            int a, b ; 161            scanf("%d %d",&a,&b);162            T[b].ins(a);163         }164         int num  = 0 ; 165         LL sum = 0 ;166         for(int i =1 ;i <= m;i ++)167         {168            scanf("%d %d",&K[i].x,&K[i].y);169         }170         sort(K+1,K+1+m,cmp);171         for(int i =1;i <= m;i ++){172            int a, b; 173            a = K[i].x;174            b = K[i].y;175            for(int j = b ;j <= 100;j ++)176            {177               ok = 0 ;178               fm = 1e9;179               T[j].f(a);180              // printf("%d %d\n",fm,ok);181               if(ok == 1)182               {183                  T[j].del(fm);184                  sum += 500*a+2*b ;185                  num ++ ; 186                  break;187               }188            }189         }190     //    for(int i =1 ;i <= 100 ;i ++)191     //        T[i].fre();192         printf("%d %I64d\n",num,sum);193    }194 return 0;195 }
View Code

 


联系
我们