自动搬运

查看原文

来自洛谷，原作者为

	zhuoqizhi 万年OI一场空，不开long long见祖宗。||莫队=离线+暴力+分块——by 算法竞赛||暂时不上洛谷，在另一个OJ上做题，私信可能不回（不是AFO）||快掉蓝了估值122

搬运于2025-08-24 21:17:05，当前版本为作者最后更新于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;
}