题解：B4099 [CSP-X2022 山东] 摧毁

zhuoqizhi · 2024-12-22 08:49:00 · 题解

题目分析

前置芝士：贪心，计数排序。

首先，我们需要考虑如何贪心：

因为使用脉冲轨道武器打一条轨道上的多少颗卫星都是 c 元，所以先用定点激光武器打若干个，再用脉冲轨道武器打完剩下的，肯定是不如用脉冲轨道武器一次性打完的。

而如果一条轨道上只有 1 颗卫星，用脉冲轨道武器要 2 元，那么用定点激光武器打比较优。

所以，如果一条轨道上的卫星个数如果小于 c 就用定点激光武器，否则用脉冲轨道武器。

接着用计数排序的思想，以数组的值为下标统计个数。

最后用一个数组储存下这个高度是否被轰炸过。

Code

#include<iostream>
#include<set>
#include<deque>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<random>
#include<ctime>
#include<climits>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define int long long
bool isprime(int x){
    if(x<=1){
        return 0;
    }
    int sq=sqrt(x);
    for(int i=2;i<=sq;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
int lcm(int x,int y){
    return x/gcd(x,y)*y;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,c;
        cin>>n>>c;
        vector<int> can(1000005)/*桶*/,has(1000005)/*是否被轰炸过*/,num;
        int ans=0;
        for(int i=0;i<n;i++){
            int tmp;
            cin>>tmp;
            can[tmp]++;//计数
            num.push_back(tmp);
        }
        for(int i=0;i<n;i++){
            if(!has[num[i]]){//判断是否被轰炸过
                if(can[num[i]]>c){//脉冲轨道武器打比较优
                    ans+=c;
                }
                else{
                    ans+=can[num[i]];//定点激光武器打比较优
                }
                has[num[i]]=1;//将同一轨道上的卫星全都标记为炸掉
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}