本文涉及知识点

C++贪心

LeetCode3273. 对 Bob 造成的最少伤害

给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。
Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。
每一秒中，在敌人对 Bob 造成伤害 之后 ，Bob 会选择 一个 还活着的敌人进行攻击，该敌人的健康值减少 power 。
请你返回 Bob 将 所有 n 个敌人都消灭之前，最少 会受到多少伤害。
示例 1：
输入：power = 4, damage = [1,2,3,4], health = [4,5,6,8]
输出：39
解释：
最开始 2 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间内对 Bob 的总伤害是 10 + 10 = 20 点。
接下来 2 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间内对 Bob 的总伤害是 6 + 6 = 12 点。
接下来 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间内对 Bob 的总伤害是 3 点。
接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间内对 Bob 的总伤害是 2 + 2 = 4 点。
示例 2：
输入：power = 1, damage = [1,1,1,1], health = [1,2,3,4]
输出：20
解释：
最开始 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间对 Bob 的总伤害是 4 点。
接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间对 Bob 的总伤害是 3 + 3 = 6 点。
接下来 3 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间对 Bob 的总伤害是 2 + 2 + 2 = 6 点。
接下来 4 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间对 Bob 的总伤害是 1 + 1 + 1 + 1 = 4 点。
示例 3：
输入：power = 8, damage = [40], health = [59]
输出：320
提示：
1 <= power <= 104
1 <= n == damage.length == health.length <= 105
1 <= damage[i], health[i] <= 104

贪心之临项交换

need[i] 记录消除第i个怪物需要的回合，need[i] = heath[i]/power + (0 != heath[i]/power)。
令某解打完第i1个怪物后 攻击第i2个怪物。 相比先打i2，再打i1。
多承受的伤害x[i2]：need[i1]*image[i2]
少承受的伤害x[i1]：need[i2]*image[i1]
如果x[i1] > x[i2]，无需交换。
need[i2]/image[i2] >need[i1]/iamge[i1] 无需交换。
即：need[i]/image[i] 升序。
性质一： 一个怪一定是连续几个回合攻击，直到消灭。令某个第i1个回合打死。将打此的怪的回合移到i1,i1-1…。此怪都是第i1回合死，其它怪可能提前死，绝对不会更晚死。

代码

核心代码

class Solution {
		public:
			long long minDamage(int power, vector<int>& damage, vector<int>& health) {
				const int N = damage.size();
				vector<long long> needs;
				for (const auto& n : health) {
					needs.emplace_back(n / power + (0 != n % power));
				}
				vector<int> indexs(N);
				iota(indexs.begin(), indexs.end(), 0);
				sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return needs[i1]* damage[i2] < needs[i2]*damage[i1]; });
				long long turn = 0, ans = 0;
				for (const auto& i : indexs) {
					turn += needs[i];
					ans += damage[i] * turn;
				}
				return ans;
			}
		};

单元测试

int power;
		vector<int> damage,  health;
		TEST_METHOD(TestMethod11)
		{
			power = 4, damage = { 1,2,3,4 }, health = { 4,5,6,8 };
			auto res = Solution().minDamage(power, damage, health);
			AssertEx(39LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			power = 1, damage = { 1,1,1,1 }, health = { 1,2,3,4 };
			auto res = Solution().minDamage(power, damage, health);
			AssertEx(20LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			power = 8, damage = { 40 }, health = { 59 };
			auto res = Solution().minDamage(power, damage, health);
			AssertEx(320LL, res);
		}