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

· · 题解

题号：P14205

题目链接：P14205 [ROI 2016 Day1] 要塞防御

题目简述：

题目一共给我们 n 个防御段，每个防御段一名士兵可以抵御的敌人数量 k_i 和每个防御段会有的敌人数量 a_i以及我们的士兵总量 s。要我们通过合理分配士兵，求出最少会有多少名敌人突破防线。

思路：

这道题很显然，我们优先选择让士兵去 k_i 更大的防御段是最优解，因为这时一名士兵所能抵御的敌人数量就更多一些。可这时，还有一个问题：

假如我们有一个会有 3 名敌人进攻的防御段，这个防御段一名士兵可以抵御 2 名敌人。那么，我们派一个人去这个防御段，这个士兵可以抵御 2 名敌人，可如果我们再派一个人去，就只能再让他抵御剩下的 1 名敌人了。

这个问题启发我们要处理最后 1 名士兵所能解决的敌人数量不是 k_i 的情况。

我们选择用 map 来记录一名士兵可以抵御的敌人数量，再从大到小选取。最后让敌人总数减去我们抵御住的敌人总数就可以了。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
    x=0;char c;int sign=1;
    do{c=getchar();if(c=='-') sign=-1;} while(!isdigit(c));
    do{x=x*10+c-'0';c=getchar();}while(isdigit(c));
    x*=sign;
}//快读增加输入效率
long long n,s;
long long a[100005],k[100005];
long long d[200005],l;
map<long long,long long> f;
bool cmp(long long s1,long long s2){
    return s1>s2;
}//从大到小排序
long long z;
int main(){
    read(n),read(s);
    for(int i=1;i<=n;i++){
        read(a[i]),read(k[i]);
        z+=a[i];//计算敌人总数
        d[++l]=k[i],d[++l]=a[i]%k[i];
        f[k[i]]+=a[i]/k[i];//记录一名士兵可以抵御k_i名敌人的数量
        f[a[i]%k[i]]++;//记录一名士兵可以抵御a_i % k_i名敌人的数量
    }
    sort(d+1,d+l+1,cmp);//贪心排序
    for(int i=1;i<=l;i++){
        if(d[i]==d[i-1]) continue;//避免重复选择
        if(f[d[i]]<=s) z-=f[d[i]]*d[i],s-=f[d[i]];//计算答案
        else z-=d[i]*s,s=0;//计算答案
    }
    cout<<z;//输出答案
    return 0;
}

总结：

本题利用 贪心 思想，总体难度不算太高，适合用作 贪心 初学者的练习题。