首页 > 代码库 > HDU4846Task treap + 贪心
HDU4846Task treap + 贪心
题意:给你 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。