hdu 4415 Assassin’s Creed

http://acm.hdu.edu.cn/showproblem.php?pid=4415

　　区域赛的一道贪心题，记当时这题是最多人做的，不过也是通过率最低的题。这题容易因为思考不够严密而导致wa。

　　题意：一个刺客要暗杀n个人，他只有一把耐久度为m的武器。杀这n个不同的人会消耗不同的耐久度A，不过也有可能获得获得这个人的武器，而且这把武器可以不消耗自己的武器的耐久度来杀B个人。问最多可以杀多少个人，而且武器消耗要尽量小！

　　贪心主要分为两种情况：第一种，尽可能多的杀掉那些不带武器的人（可以顺便算上是否能杀掉一个带有武器的人）。第二种，因为假如可以杀掉一个带武器的人，就意味着可以杀掉所有带武器的人，而且这时必定还有多余的武器以及耐久度。第二种情况中，多余的武器都用来杀没带武器，却要消耗最多的人。如果耐久度也有剩余怎么办？明显是要继续杀剩下的人咯！这时剩下的一定是没有武器的人，有武器的搜杀光了。剩下的就是抉择是要直接杀了没带武器的呢，还是杀带有武器的来代替他！显然，如果带武器的消耗比较少，那么杀他来节省一个单位的武器用来杀那个不能提供武器的人了！

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cassert>
  5 #include <vector>
  6 
  7 using namespace std;
  8 
  9 typedef pair<int, int> pii;
 10 typedef vector<pii> vpii;
 11 typedef __int64 ll;
 12 
 13 vpii Zero, nonZero;
 14 
 15 void deal(int cc) {
 16     int n, m;
 17 
 18     Zero.clear();
 19     nonZero.clear();
 20 
 21     scanf("%d%d", &n, &m);
 22     while (n--) {
 23         int a, b;
 24 
 25         scanf("%d%d", &a, &b);
 26         if (b) {
 27             nonZero.push_back(make_pair(a, b));
 28         } else {
 29             Zero.push_back(make_pair(a, b));
 30         }
 31     }
 32 
 33     sort(nonZero.begin(), nonZero.end());
 34     sort(Zero.begin(), Zero.end());
 35 
 36     int cnt1 = 0;
 37     ll cost1 = 0;
 38     vpii::iterator ii = Zero.begin();
 39 
 40     while (ii != Zero.end() && m - cost1 >= (*ii).first) {
 41         cnt1++;
 42         cost1 += (*ii).first;
 43         ii++;
 44     }
 45     if (nonZero.size() && m - cost1 >= nonZero[0].first) {
 46         cost1 += nonZero[0].first;
 47         cnt1 += (int)nonZero.size();
 48     }
 49 //printf("cnt %d  cost %I64d\n", cnt1, cost1);
 50 
 51     int cnt2 = 0, rest = 0;
 52     ll cost2 = 0;
 53     ii = nonZero.begin();
 54 
 55     if (nonZero.size() && m >= (*ii).first) {
 56         cost2 = (*ii).first;
 57         cnt2 = 1;
 58         rest = (*ii).second;
 59         ii++;
 60 
 61         while (ii != nonZero.end()) {
 62             rest += (*ii).second - 1;
 63             cnt2++;
 64             ii++;
 65         }
 66     }
 67 //printf("cnt %d  cost %I64d\n", cnt2, cost2);
 68     cnt2 += min(rest, (int)Zero.size());
 69 
 70     int size1 = (int)Zero.size() - min(rest, (int)Zero.size());
 71     int size2 = (int)nonZero.size();
 72 
 73     for (int i = 0, j = 1; i + j <= size1;) {
 74         if (j < size2) {
 75             if (m - cost2 >= min(Zero[i].first, nonZero[j].first)) {
 76                 if (Zero[i].first > nonZero[j].first) cost2 += nonZero[j].first, j++;
 77                 else cost2 += Zero[i].first, i++;
 78                 cnt2++;
 79             } else break;
 80         } else {
 81             if (m - cost2 >= Zero[i].first) cost2 += Zero[i].first, cnt2++, i++;
 82             else break;
 83         }
 84     }
 85 //printf("cnt %d  cost %I64d\n", cnt2, cost2);
 86 
 87     printf("Case %d:", cc);
 88     if (cnt1 > cnt2 || (cnt1 == cnt2 && cost1 < cost2)) {
 89         printf(" %d %I64d\n", cnt1, cost1);
 90     } else {
 91         printf(" %d %I64d\n", cnt2, cost2);
 92     }
 93 }
 94 
 95 int main() {
 96     int T;
 97 
 98 freopen("in", "r", stdin);
 99     scanf("%d", &T);
100     for (int i = 1; i <= T; i++) {
101         deal(i);
102     }
103 
104     return 0;
105 }

　　贪心的题依然不强，要加紧练习了！

——written by Lyon