HDU-4864-Task-白红宇

HDU-4864-Task

阅读量：6096 次

发布时间：2019-06-20

本文共 1346 字，大约阅读时间需要 4 分钟。

链接：https://vjudge.net/problem/HDU-4864

题意：

给n个机器，m个任务。每个机器有运行时间和等级，每个任务执行时间和等级。

每个机器每天只能用一次，同时运行时间不能超过给定值。

能执行的任务的等级不能高于机器的等级。

执行一个任务能得到500*x + 2 * y的钱，求最多能得到多少钱。

思路:

贪心，按照先x后y的降序排列。

从大到小选择事件够的机器记录，

再每次从y往最大100来找第一个满足的机器执行某个任务。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long LL;const int MAXN = 1e5 + 10;struct Node{ int _x; int _y; bool operator < (const Node & that) const { return this->_x > that._x||(this->_x == that._x && this->_y > that._y); }}machine[MAXN], task[MAXN];int level[200];int main(){ int n, m; while (~scanf("%d%d", &n, &m)) { memset(level, 0, sizeof(level)); for (int i = 1;i <= n;i++) scanf("%d%d", &machine[i]._x, &machine[i]._y); for (int i = 1;i <= m;i++) scanf("%d%d", &task[i]._x, &task[i]._y); sort(machine + 1, machine + 1 + n); sort(task + 1, task + 1 + m); LL res = 0; int cnt = 0; for (int i = 1,j = 1;i <= m;i++) { while (j <= n && machine[j]._x >= task[i]._x) { level[machine[j]._y]++; j++; } for (int k = task[i]._y;k <= 100;k++) { if (level[k] != 0) { cnt++; res += 500 * task[i]._x + 2 * task[i]._y; level[k]--; break; } } } printf("%d %lld\n", cnt, res); } return 0;}