CF1891C. Smilo and Monsters 题解
SunnyYuan
·
·
题解
建议标签：贪心
思路
贪心题，首先我们可以想到可以使用较小的怪物群组合出 x 然后用 1 的代价干掉当前最大的怪物群，直到所有较小的怪物加起来都不能干掉最大的怪物时，才要特判。
当所有较小的怪物加起来都不能干掉最大的怪物时，如果当前已经积累了 x 个怪物，现在只剩下一个最大的怪物群，有 t 只怪物，那么我们不妨将他们两个加起来考虑。
## 代码
```cpp
/*******************************
| Author: SunnyYuan
| Problem: C. Smilo and Monsters
| OJ: Codeforces - Codeforces Round 907 (Div. 2)
| URL: https://codeforces.com/contest/1891/problem/C
| When: 2023-11-01 10:03:36
|
| Memory: 256 MB
| Time: 1000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
sort(a.begin(), a.end());
int l = 0, r = n - 1, sum = 0;
i64 ans = 0;
while (l <= r) {
while (l < r && sum < a[r]) {
int add = min(a[r] - sum, a[l]);
sum += add;
a[l] -= add;
if (!a[l]) l++;
}
if (sum == a[r]) {
ans += sum + 1;
a[r] = sum = 0;
r--;
}
if (l == r) {
// cout << l << ' ' << r << ' ' << a[l] << endl;
int p = sum + a[l];
if (p & 1) ans += (p / 2) + 1 + (bool)(p / 2);
else ans += (p / 2) + 1;
break;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
```