题解：P14205 [ROI 2016 Day1] 要塞防御

· · 题解

贪心。

显然优先守卫 k_i 更大的防御段，这样单个士兵的贡献更高。

但是该段最后可能剩下不到 k_i 个敌人，此时最后一个个士兵的贡献会减少。

于是我们使用 map 统计贡献为 x 的士兵数量 y，优先选贡献更大的士兵。

在一个防御段中，前 \big \lfloor \frac{a_i}{k_i} \big \rfloor 个士兵的贡献为 k_i，最后一个士兵的贡献为 a_i \bmod k_i。

按贡献排序后，用敌人总个数减去消灭掉的敌人个数即可。

参考代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define PLL pair<ll, ll>

const int N = 300050;

int n, s, a, k;
ll ans;
map<ll, ll> mp;
vector<PLL> cnt;

bool cmp(PLL a, PLL b){
    return a.first > b.first;
}

int main() {
    cin >> n >> s;
    for(int i = 1; i <= n; i ++){
        cin >> a >> k;
        ans += a;
        mp[k] += a / k;
        mp[a % k] ++;
    }
    for(PLL i : mp)
        cnt.push_back(i);
    sort(cnt.begin(), cnt.end(), cmp);
    for(PLL i : cnt){
        if(i.second < s){
            s -= i.second;
            ans -= i.first * i.second;
        }
        else{
            ans -= s * i.first;
            break;
        }
    }
    cout << ans;
    return 0;
}