1≤N≤10 6 ,1≤M≤10 6 ,1≤N∗M≤10 8
时间: 2024-05-18 09:12:33 浏览: 10
在这种情况下,使用动态规划的时间复杂度会达到 $O(NM)$,无法通过本题。因此,我们需要寻求其他解决方法。
观察题目可以发现,卡牌的点数和伤害值都比较小,因此我们可以考虑使用桶排序和贪心算法来解决问题。
具体来说,我们可以先将卡牌按照点数从小到大排序,然后从小到大枚举每张卡牌,尽可能地用它来攻击敌人。具体来说,对于第 i 张卡牌,我们可以计算出它最多可以攻击敌人的次数 cnt,然后用 cnt 次这张卡牌攻击敌人,并将 cnt 张这张卡牌从手牌中删除。最后,如果敌人还没有被消灭,则无法获得最大剩余点数之和。
时间复杂度为 $O(N+M)$,可以通过本题。以下是代码实现:
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 5;
int n, m;
int a[MAXN], cnt[MAXN];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
sort(a + 1, a + n + 1);
int ans = 0, damage = 0;
for (int i = 1; i <= n; i++) {
if (damage >= m) break;
if (cnt[a[i]] == 0) continue;
int t = min((m - damage) / a[i], cnt[a[i]]);
ans += cnt[a[i]] - t;
cnt[a[i]] = t;
damage += cnt[a[i]] * a[i];
}
if (damage < m) ans = -1;
cout << ans << endl;
return 0;
}
```
时间复杂度为 $O(N+M)$。