力扣3273.对Bob造成的最少伤害
-
贪心
- 考虑每个敌人对答案的贡献
- 对于敌人AB：先杀A所受伤害为tA * dA + (tA + tB) * dB
- 先杀B所受伤害为tB * dB + (tA + tB) * dA
- 因此如果tA * dB < tB * dA
- 就先杀A
-
class Solution {public:long long minDamage(int power, vector<int>& damage, vector<int>& health) {int n = health.size();vector<pair<int,int>> a(n);for(int i=0;i<n;i++)a[i] = {(health[i] - 1) / power + 1,damage[i]};//按照公式排序ranges::sort(a,[](const auto &p,const auto &q){return p.first * q.second < q.first *p.second;});//s记录累积时间long long ans = 0,s = 0;//对于每个敌人的贡献 = 存活天数 * 伤害for(auto &[k,d] : a){s += k;ans += s * d;}return ans;}};
