ʕ·͡ˑ·ཻ ʕ•̫͡• ʔ•̫͡•ཻʕ•̫͡•ʔ•͓͡•ʔ

题目 - Task

Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500xi+2yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

Input

The input contains several test cases.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.
The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.

Output

For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.

Sample Input

1
2
3
4
1 2
100 3
100 2
100 1

Sample Output

1
1 50004

题意：

​ m个任务，每一个任务包括需要的时间和完成的难度，n台机器，每台任务有工作的最大时间和可以完成的任务的最大难度。完成一个任务可以获得奖金，最大时间>=任务的时间，最大难度>=任务的难度，这里要注意每个任务只能由一台机器完成，每台机器只能完成一个任务，要求：完成尽量多的任务，多种情况的时候，尽量使得奖金最多。

解题：

​ 之前弄清题目意思，没有注意到每个任务只能由一台机器完成，每台机器只能完成一个任务。

​ 弄清之后，可以这样考虑这道题，对于每个任务和机器不论是时间还是难度都从大到小排序，对于每个任务而言来找满足条件的机器，选择最大难度最小的那个，因为在找机器的过程是从大到小的所以在时间上是满足条件的，但难度就不一定所以，先用难度小的，保留难度大的。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<string.h>
#include<algorithm>

using namespace std;

struct node {
	int x, y;
}a[100005], b[100005];

int vis[100005];

bool cmp(node a, node b) {
	if(a.x != b.x) return a.x > b.x;
	else return a.y > b.y;
}

int main() {
	int n, m;
    //这里要注意，多组测试样例
	while(~scanf("%d %d",&n,&m)) {
	int ans = 0;
    //注意sum可能超出int型范围
	long long sum = 0;
	for(int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].x, &a[i].y);
	}
	for(int i = 0; i < m; i++) {
		scanf("%d %d", &b[i].x, &b[i].y);
	}
	sort(a, a + n, cmp);
    //这里写成了加n所以wa了
	sort(b, b + m, cmp);
	memset(vis,0,sizeof(vis));
	int j = 0;
	for(int i = 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 += 500 * b[i].x + 2 * b[i].y;
				break;
			}
		}
	}
	cout<<ans<<" "<<sum<<endl;
}
	return 0;
}

 Previous

贪心