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

yueyan_WZF · 2025-10-15 15:33:00 · 题解

这是一道简单的贪心。

首先我们可以先计算出如果想要将所有敌人全部防住需要多少守卫，记为 sum，如果 sum \le s 那么可以直接全部防住。

那么如果大于呢？

我们肯定是要在一些要塞中减少守卫的数量，每个要塞减少一个守卫的话会放进 k_i 名敌人，那么我们只需要按 k_i 排下序，贪心的选取前 sum-s 个就行了。

细节提示： 由于有的时候 a_i 不是 k_i 的倍数，那就意味着在这个要塞中有一个守卫撤走的话，会放进去少于 k_i 个敌人。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+20;
int n;
int sum;
int s;
int ans;
struct node{
    int a,k,x;
}z[N];
struct poi{
    int v,s;
}a[N];
bool cmp(poi x,poi y){
    return x.v<y.v;
}
int tot;
signed main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>z[i].a>>z[i].k;
        if(z[i].a%z[i].k!=0) z[i].x=z[i].a/z[i].k+1,a[++tot].s=1,a[tot].v=z[i].a%z[i].k,a[++tot].s=z[i].x-1,a[tot].v=z[i].k;
        else z[i].x=z[i].a/z[i].k,a[++tot].s=z[i].x,a[tot].v=z[i].k;
       sum+=z[i].x;
    }
    if(sum<=s){
        cout<<"0";
        return 0;
    }
    int t=sum-s;
   sort(a+1,a+1+tot,cmp);
   for(int i=1;i<=tot;i++){
        if(a[i].s>=t){
            ans+=t*a[i].v;
            break;
        }
        else{
            ans+=a[i].s*a[i].v;
            t-=a[i].s;
        }
   }
    cout<<ans;
    return 0;
}