专栏文章

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

yyueyan_WZF
P14205题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlq88e
此快照首次捕获于
2025/12/02 04:28
3 个月前
此快照最后确认于
2025/12/02 04:28
3 个月前
查看原文
这是一道简单的贪心。
首先我们可以先计算出如果想要将所有敌人全部防住需要多少守卫，记为 sumsum，如果 sum≤ssum \le s 那么可以直接全部防住。
那么如果大于呢？
我们肯定是要在一些要塞中减少守卫的数量，每个要塞减少一个守卫的话会放进 kik_i 名敌人，那么我们只需要按 kik_i 排下序，贪心的选取前 sum−ssum-s 个就行了。
细节提示： 由于有的时候 aia_i 不是 kik_i 的倍数，那就意味着在这个要塞中有一个守卫撤走的话，会放进去少于 kik_i 个敌人。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...