贪心之 hdu 4864

//  [7/23/2014 Sjm]
/*
又坑在TLE上了。。。。
Each machine can only complete a task one day. Each task can only be completed by one machine.所以想到了贪心。。。
 
发现 dollars = 500*xi+2*yi, 由于 xi(0<xi<1440),yi(0=<yi<=100)， 500*1 > 2*100，所以 dollars 的决定因素是需要的时间，
那么就尽可能先解决需要时间多的任务，同时选择的时间和难度水平尽可能接近任务的机器，如此即可求得最优解。
 
不过，先前写的代码一直TLE，后来用 Judge[101][1441] 做一个预处理，AC。。。。
*/

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cstring>
 6 using namespace std;
 7 typedef __int64 int64;
 8 const int MAX = 100005;
 9 int N, M, len;
10 
11 struct node {
12     int time;
13     int lev;
14 };
15 
16 bool Cmp(const node n1, const node n2) {
17     if (n1.time == n2.time) {
18         return n1.lev > n2.lev;
19     }
20     else {
21         return n1.time > n2.time;
22     }
23 }
24 
25 node task[MAX];
26 int Judge[101][1441];
27 
28 void Solve()
29 {
30     int num = 0;
31     int64 money = 0;
32     for (int i = 0; i < M; ++i) {
33         for (int j = task[i].lev; j <= 100; ++j) {
34             int k;
35             for (k = task[i].time; k <= 1440; ++k) {
36                 if (Judge[j][k]) {
37                     Judge[j][k]--;
38                     num++;
39                     money += (500 * task[i].time + 2 * task[i].lev);
40                     break;
41                 }
42             }
43             if (k != 1441) {
44                 break;
45             }
46         }
47     }
48     printf("%d %I64d
", num, money);
49 }
50 
51 int main()
52 {
53     //freopen("input.txt", "r", stdin);
54     while (~scanf("%d %d", &N, &M)) {
55         memset(Judge, 0, sizeof(Judge));
56         int x, y;
57         for (int i = 0; i < N; ++i) {
58             scanf("%d %d", &x, &y);
59             Judge[y][x]++;
60         }
61         for (int i = 0; i < M; ++i) {
62             scanf("%d %d", &task[i].time, &task[i].lev);
63         }
64         sort(task, task + M, Cmp);
65         Solve();
66     }
67     return 0;
68 }

贪心 之 hdu 4864

贪心之 hdu 4864