腾讯 编程 机器和 任务题解法（很多贴的贪心解法是错的）

本是一个最大匹配下，收益最大问题。 正规解法是 二分图，添加源汇点，跑最大费用最大流，TMD 点100000个，必超时。 结论--->这题有问题。出题人。。。拿了N年前多校错题搬过来。。

原题的公式的500*xi+2*yi   yi范围是０-100  他的公式是200*xi+3*yi      yi范围是０-100

大佬，这题在牛客哪地方啊，我想做做看，找不到啊😂

我的贪心思路是，用最差的机器完成当前他能完成的收益最高的任务。可是WA40%，不知道为什么，感觉很完美。 #include <bits/stdc++.h> #define MEM(a,b) memset(a, b, sizeof(a)) using namespace std; typedef long long LL; typedef pair<int,int> pii; struct Node {     int t, val;     Node() {}     Node(int t, int v) : t(t), val(v) {}     bool operator < (const Node& o) const {         int x1 = 200 * t + 3 * val;         int x2 = 200 * o.t + 3 * o.val;         return x1 < x2;     } }; priority_queue<Node>q; int task[2010][110]; int mach[2010][110]; int main() {     int n, m, x, y;     scanf("%d%d", &n, &m);     for(int i = 0; i < n; ++ i) {         scanf("%d%d", &x, &y);         mach[x][y]++;     }     for(int i = 0; i < m; ++ i) {         scanf("%d%d", &x, &y);         task[x][y]++;     }     LL sum_task = 0, sum_val = 0;     for(int i = 1; i < 1440; ++ i) {         for(int j = 0; j <= 100; ++ j) {             while(task[i][j]--) {                 q.push(Node(i, j));             }             while(mach[i][j]--) {                 if(!q.empty()) {                     Node top = q.top();                     q.pop();                     sum_task++;                     sum_val += 1LL * 200 * top.t + 1LL * 3 * top.val;                 }             }         }     }     cout << sum_task << ' ' <<sum_val << endl;     return 0; }

贪心和DP什么的感觉好难啊

可以贪心做。先对机器进行贪心算法，按照从小到大排序，然后对任务从大到小贪心，每次选择满足当前剩余最大任务的资源最小的机器即可。如果不对机器从小太大排，可能后面的时间少但是难度大的任务没有机器去做。