[贪心] HDU 4864 Task

题意

有n个机器有m个任务，需要机器x和y都要大于等于任务的x，y就能得到500*x+2*y的任务报酬，问最多能够解决多少任务，一共能够获得多少报酬。

思路

先保证数量最多，再保证钱数最大 按照x降序排列， x相同的时候按照y降序排列， 这样就可以保证钱数最多 对于一个工作我们可以选择的是所有x1>x的机器， 而在这些机器中我们选择最小的y1， 这样可以保留比较大的y1使其去匹配后面的任务， 而x1则完全不用操心， 他肯定可以匹配后面的任务， 因为任务是按照x降序排列的

开始卡在怎样在x足够的时候选最小的y上，看了代码才明白 要对每一个task遍历，寻找可以匹配的machine

代码

// https://www.cnblogs.com/xingxing1024/p/5273176.html #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; typedef long long ll; const int maxn = 100000 + 10; const int maxlv = 110; struct Node { int t, lv; //降序排列，按照任务所花费时间从大到小排序,保证任务数完成的最多 bool operator< ( const Node &rhs ) const { if ( t == rhs.t ) return lv > rhs.lv; return t > rhs.t; } } mach[ maxn ], task[ maxn ]; int n, m; // machine,task; int level[ maxlv ]; void Inpt () { for ( int i = 0; i < n; ++i ) { int t, y; scanf ( "%d%d", &t, &y ); mach[ i ] = ( Node ){t, y}; } for ( int i = 0; i < m; ++i ) { int t, y; scanf ( "%d%d", &t, &y ); task[ i ] = ( Node ){t, y}; } } void Solve () { memset ( level, 0, sizeof ( level ) ); int num = 0; ll money = 0; int j = 0; // machines_that_can_complete_current_task for ( int i = 0; i < m; ++i ) { while ( j < n && mach[ j ].t >= task[ i ].t ) level[ mach[ j++ ].lv ]++; //从当前能完成该任务的机器里挑选lv最小的那个 for ( int k = task[ i ].lv; k < maxlv; ++k ) if ( level[ k ] ) { ++num; money += 500 * task[ i ].t + 2 * task[ i ].lv; level[ k ]--; break; } } printf ( "%d %lld\n", num, money ); } int main () { while ( ~scanf ( "%d%d", &n, &m ) ) { Inpt (); sort ( mach, mach + n ); sort ( task, task + m ); Solve (); } return 0; }