首页 > 代码库 > HDU 4864 Task

HDU 4864 Task

题意: 每台机器有x,y两种属性,有m个任务。假设机器的这两个属性大于任务,那么就是能够完毕这个任务,而且每一个任务每仅仅能完毕一个任务。
思路:先依照x排序,x相等,依照y排序,每一次记录下来能够完毕这个任务的机器。寻找属性相差最小的那台。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define N 111111

struct node{
    int x,y;
    ll ac;
    void input(){
     scanf("%d%d",&x,&y);
     ac = 500*x+2*y;
    }
}a[N],b[N];


bool cmp(node xx,node yy){
   if(xx.x==yy.x) return xx.y>yy.y;
   return xx.x>yy.x;
}

int n,m;
int vis[111];

int main(){
    while(scanf("%d%d",&n,&m)==2){
        for(int i=0;i<n;i++)
            a[i].input();
        for(int j=0;j<m;j++)
            b[j].input();
        sort(a,a+n,cmp);
        sort(b,b+m,cmp);
        ll sum = 0;
        int ans =0;
        memset(vis,0,sizeof(vis));
        for(int i=0,j=0;i<m;i++){
            while(j<n&&a[j].x>=b[i].x){
                vis[a[j].y]++;
                j++;
            }
            for(int k=b[i].y;k<=100;k++){
                if(vis[k]){
                vis[k]--;
                ans++;
                sum+=b[i].ac;
                break;
                }
            }
        }
        printf("%d %I64d\n",ans,sum);

    }
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

HDU 4864 Task