hdu4864 hdu4268 贪心 lower

hdu4864

题意：

有n个机器，m个任务，n,m<=100000，每个机器都有工作时间的最大限制xi(0<xi<1440)和完成的最大难度yi(0<=yi<=100)，每个任务也有所需要的时间和难度，只要机器的时间大于等于任务，难度大于等于任务，该任务就可以被机器完成，每完成一个任务就可以得到500*xi+2*yi的money，问最多能有多少个任务被完成，并且保证完成任务数量最多的情况下，所得到的money最多是多少？

思路：

由于money是500*x+2*y，而y最大是100，则只要保证任务的x最大，那么得到的钱一定是最多的。

将任务按照时间x从大到小排序，然后依次用任务查找机器，时间x从大到小保证了得到的钱是最多的，然后每个任务找出大于该任务难度y且与难度y最接近的机器完成该任务。现在有个问题需要证明一下，每次找难度最接近的机器，那么时间x只是大于任务x即可，时间是否物尽其用了呢？是否有浪费呢？不会，因为任务的x是从大到小排序遍历，如果任务找到了一个大于自身时间x的机器，就用，即使有别的x更大的机器没有被用，但是可以留下来给别的任务用。

比赛的时候代码WA，虽然也是贪心，但是用的机器查找任务，导致x做到了物尽其用，y并没有做到，so WA~

不要迷迷糊糊的写，要严谨的证明全对再下手写~

 /*===============================================================

 *   Copyright (C) 2014 All rights reserved.

 *

 *   File Name: hdu4864.cpp

 *   Author:sunshine

 *   Created Time: 2014年07月23日

 *

 ================================================================*/

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <math.h>

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define N 100005

 struct node{

     int x,y;

     bool operator < (const node &n1) const{

         if(x != n1.x) return x > n1.x;

         return y > n1.y;

     }

 }task[N];

 int main(){

     int n,m;

     int x,y;

     while(cin >> n >> m){

         multiset<int> S[];

         long long res = ;

         int cnt = ;

         for(int i = ;i < n;i ++){

             scanf("%d%d", &x, &y);

             S[y].insert(x);

         }

         for(int i = ;i < m;i ++){

             scanf("%d%d", &task[i].x, &task[i].y);

         }

         sort(task,task+m);

         for(int i = ;i < m ;i ++){

             x = task[i].x;

             y = task[i].y;

             for(int j = y;j <= ;j ++){

                 if(S[j].empty()) {

                     continue;

                 }

                 multiset<int>::iterator it = S[j].lower_bound(x);

                 if(it == S[j].end() || *it < x){

                     continue;

                 }else{

                     cnt ++;

                     res +=  * x +  * y;

                     S[j].erase(it);

                     break;

                 }

             }

         }

         printf("%d %I64d\n",cnt,res);

     }

     return ;

 }

hdu4268

题意：

Alice有n个纸片，Bob有n个纸片，n<=100000每个纸片有长度和宽度，已知这2*n个纸片的长和宽，求Alice最多能覆盖Bob多少张纸片，每张纸片只能被用一次。

思路：

将这2*n张纸片按照长x从大到小排序，y从大到小排序，如果x、y相等，则Alice的纸片排在前面，用Bob去查找Alice，即Alice所有的纸片插入到set中，但是并不是一下子全部插入到set中，而是边插入set处理边求解Bob的第i张纸片能否被覆盖，这样能够保证之前插入的所有纸片的长x都大于等于自身的x，每次遇到Alice的纸片则插入到set中，每次遇到Bob的纸片则在set中查找刚好大于等于y的第一个Alice的纸片，然后把它删除，依次。

 /*===============================================================

 *   Copyright (C) 2014 All rights reserved.

 *

 *   File Name: hdu4268.cpp

 *   Author:sunshine

 *   Created Time: 2014年07月23日

 *

 ================================================================*/

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <math.h>

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define N 100010

 struct node{

     int x,y;

     bool id;

 }p[*N];

 int cmp(node n1,node n2){

     if(n1.x == n2.x && n2.y == n2.y) return n1.id > n2.id;

     if(n1.x != n2.x) return n1.x > n2.x;

     return n1.y > n2.y;

 }

 int main(){

     int cas;

     int n;

     int x,y;

     scanf("%d", &cas);

     while(cas --){

         scanf("%d", &n);

         for(int i = ;i < n;i ++){

             scanf("%d%d", &p[i].x, &p[i].y);

             p[i].id = ;

         }

         for(int i = n;i <  * n;i ++){

             scanf("%d%d", &p[i].x, &p[i].y);

             p[i].id = ;

         }

         sort(p,p +  * n,cmp);

         multiset<int>S;

         int cnt = ;

         for(int i = ;i <  * n;i ++){

             if(p[i].id){

                 S.insert(p[i].y);

             }else{

                 y = p[i].y;

                 multiset<int>::iterator it = S.lower_bound(y);

                 if(it == S.end() || *it < y){

                     continue;

                 }else{

                     S.erase(it);

                     cnt ++;

                 }

             }

         }

         printf("%d\n",cnt);

     }

     return ;

 }

巴特西

hdu4864 hdu4268 贪心 lower_bound

最新文章

热门文章