小码哥学多重集

多重集：可以包含重复的元素

多重集S包含n个不同的非负整数

允许对该多重集进行K次操作

问：这个集中最大的数是什么 设其为max，

核心：找出没有出现的最小非负整数

没有出现的最小非负整数是什么 设其为min

（max + min)/2 然后向上取整 insert 到list中

算出K次操作后S中，不同元素的个数

不同元素：

挨个遍历，如果这个数第一次出现，就num++ ，如果是比一多的出现次数就忽略

利用set的特性，存储相同元素的唯一值

本质问题

是最后一起输出，还是可以先输入一组，再输出一组，再输入一组，再输出一组

优先选择下边的，因为简单，还节省空间

第一版代码，没有考虑输出问题，而且逻辑也有问题

#include

using namespace std;

vector arr;
int n,num;
int a;
double sum_num, max_num, min_num;

int i = 1;
void find_up(int k)
{
	if(i <= k){
		bool flag = 0;
		
		double max_num = *max_element(arr.begin(), arr.end());
		for(int i=0;i<=max_num;i++)
		{
			for(int j=0;j s(arr.begin(), arr.end());
	arr.assign(s.begin(), s.end());
	num = arr.size();
}

int main(){
	int t;     //一共要测试多少组数
	int k;  //n表示多重集初始有多少个数  k表示要进行多少次操作 
	cin >> t;
	for(int i=1;i<=t;i++) 
	{
		cin >> n >> k;
		for(int j=1;j<=n;j++)
		{
			cin >> a;
			arr.insert(arr.end(), a);
		} 
	}	

	find_up(k);
	dif_num();	
	cout << num;
	return 0;
}

第二版代码  答案错误，

可能是没有考虑本质问题

是最后一起输出

优先选择下边的，因为简单

还是可以先输入一组，再输出一组，再输入一组，再输出一组

#include

using namespace std;

vector arr;
int n, num;
int a;  //5月20日下午 4：30-6：30   下周五 
double sum_num, max_num, min_num;

int i = 1;
void find_up(int k)
{
	if(i <= k){
		sort(arr.begin(),arr.end());
		bool flag = 0;
		
		double max_num = *max_element(arr.begin(), arr.end());
		double min_num = *min_element(arr.begin(), arr.end());
	
		if(min_num == 0){
			for(int i=0;i s(arr.begin(), arr.end());
	arr.assign(s.begin(), s.end());
	num = arr.size();
}

int main(){
	int t;     //一共要测试多少组数
	int k;     //n表示多重集初始有多少个数  k表示要进行多少次操作 
	cin >> t;
	for(int i=1;i<=t;i++) 
	{
		cin >> n >> k;
		for(int j=1;j<=n;j++)
		{
			cin >> a;
			arr.insert(arr.end(), a);
		} 
	}	
	
	if(arr[0] != 0){
		min_num = 0;
	}
	else{
		find_up(k);	
	}
	
	dif_num();	
	cout << num;
	
//	for(int i=0;i

最后一个问题，多组数据如何同时输出

方法一：伪输出，你可以每输入一次数据就处理一次，然后输出一次

方法二：为结果开辟存储空间，等待所有的运算全部结束后一起输出

先试试方法一

方法一可以过就不用方法二

为啥？因为，懒。

方法二费脑子，还费空间

那么，方法二如何操作

现在的bug是不管我输入多少组数据，最终只处理最后一次输入的数据

猜测 数组的存储问题， 一组数据输入完成后应该马上进行运算，输出结果，然后清空，为下一次的输入腾出空间

 方法一不行，超时了，换方法二

然后，方法二每运算一次，就要进行一次数组清空和num归零

#include

using namespace std;

vector arr;
int n, num;
int a;  //5月20日下午 4：30-6：30   下周五 
double sum_num, max_num, min_num;

int var = 1;
void find_up(int k)
{
	if(var <= k){
		sort(arr.begin(),arr.end());
		bool flag = 0;
		
		double max_num = *max_element(arr.begin(), arr.end());
		double min_num = *min_element(arr.begin(), arr.end());
	
	//1 7 4 6 8 0 2 5 3 9
	//0 1 2 3 4 5 6 7 8 9 
		if(min_num == 0){
			for(int i=0;i s(arr.begin(), arr.end());
	arr.assign(s.begin(), s.end());
	num = arr.size();
}

int main(){
	vector arr2;
	int t;     //一共要测试多少组数
	int k;     //n表示多重集初始有多少个数  k表示要进行多少次操作 
	cin >> t;
		for(int i=1;i<=t;i++) 
		{
			
			cin >> n >> k;
			for(int j=1;j<=n;j++)
			{
				cin >> a;
				arr.insert(arr.end(), a);
			} 
			
			find_up(k);	
			dif_num();	
			cout << num< 
代码四：
 
自己测试用例可以通过，上机会超时，全部通不过，再想想，可能是哪个极端情况没想到，会有解决办法的
 
超时的原因是，当
 
#include

using namespace std;

vector arr;
int n, num;
double sum_num, max_num, min_num;

int var = 1;
void find_up(int k)
{
	if(var <= k){
		sort(arr.begin(),arr.end());
		bool flag = 0;
		
		double max_num = *max_element(arr.begin(), arr.end());
		double min_num = *min_element(arr.begin(), arr.end());
	
		if(min_num == 0){
			for(int i=0;i s(arr.begin(), arr.end());
	arr.assign(s.begin(), s.end());
	num = arr.size();
}


int main(){
	vector arr2;
	int a; 
	int t;     //一共要测试多少组数
	int k;     //n表示多重集初始有多少个数  k表示要进行多少次操作 
	cin >> t;
		for(int i=1;i<=t;i++) 
		{
			
			cin >> n >> k;
			for(int j=1;j<=n;j++)
			{
				cin >> a;
				arr.insert(arr.end(), a);
			} 
			
			find_up(k);	
			dif_num();	
			arr2.insert(arr2.end(),num); 
			
			arr.clear();
			num = 0;
			var = 1; 
		}	
		
		for(int i=0;i