每日一题：Assassin’s Creed

题目

有 $n$ 个敌人，你现在的武器的耐久度为 $m$,杀每个敌人要消耗 $a_i$ 点耐久度，同时得到可以再杀死 $b_i$ 个人的权利。问最多可以杀死多少人，在杀人最多的情况下最少要消耗多少耐久度？

Solution

首先会想到对人进行分类，一类是 $b_i$ 为 $0$ 的，一类是 $b_i$ 不为 $0$ 的。

杀死一个 $b_i$ 不为 $0$ 的，一定能杀死所有 $b_i$ 不为 $0$ 的，而且还能再额外杀死 $b_i$ 为 $0$ 的，显然只要杀 $a_i$ 最小的那个人即可。

分两种情况：

1. 只杀 $b_i$ 为 $0$ 的，可能原因：没有 $b_i$ 不为 $0$ 的，或者耐久度不够，或者消耗耐久度过大，还不如直接杀 $b_i$ 为 $0$ 来的划算。

2. 杀一个 $b_i$ 不为 $0$的，且消耗耐久度最小的，那么所有的 $b_i$ 不为 $0$ 都将被杀死，额外的免费杀人机会都拿来杀 $b_i$ 为 $0$ 的，用剩下的耐久度从小到大杀剩下的怪即可。但这样有缺陷，可能存在手动杀 $b_i$ 不为 $0$ 的人会更划算，因为这个怪可能消耗的耐久度非常小，而你用这次机会杀 $b_i$ 为 $0$ 的人可能消耗非常大。于是得出结论：所有 $b_i$ 不为 $0$ 的人肯定会被杀死，但我只要把所有的怪按耐久度从小到大杀即可。

两种情况取最大值即可。

Code

#include <bits/stdc++.h>
using namespace std;
vector<int> g1, g2, g3;
int main() {
  int t, n, m, x, y, c = 0;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    g1.clear();
    g2.clear();
    g3.clear();
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", &x, &y);
      if (y) 
        g1.push_back(x);
      else
        g2.push_back(x);
      sum+=y;
    }
    sort(g1.begin(), g1.end());
    sort(g2.begin(), g2.end());
    int cost1 = 0, cost2 = 0, num1 = 0, num2 = 0;
    for (int i = 0; i < g2.size(); i++) {
      if (cost1 + g2[i] > m) break;
      cost1 += g2[i];
      num1++;
    }
    if (g2.size() == n || m < g1[0])
      printf("Case %d: %d %d\n", ++c, num1, cost1);
    else {
      cost2 = g1[0];
      sum++;
      num2 = min(sum, n);
      for (int i = 0; i < g2.size(); i++) g3.push_back(g2[i]);
      for (int i = 1; i < g1.size(); i++) g3.push_back(g1[i]);
      sort(g3.begin(), g3.end());
      for (int i = 0; i < g3.size(); i++) {
        if (num2 >= n || cost2 + g3[i] > m) break;
        cost2 += g3[i];
        num2++;
      }
      if (num1 > num2 || num1 == num2 && cost1 < cost2)
        printf("Case %d: %d %d\n", ++c, num1, cost1);
      else
        printf("Case %d: %d %d\n", ++c, num2, cost2);
    }
  }
  return 0;
}