快乐集合

第一行为t (1 ≤ t ≤ 100) ，代表 t 组测试用例

每组测试用例的第一行包含两个数

,其中n为集合的大小，k为操作次数

每组测试用例的第二行包含n个不同的数

为快乐集合中的数

可以保证所有测试用例的n的和不超过10⁵

Java 解法, 执行用时: 471ms, 内存消耗: 96964K, 提交时间: 2021-05-25 10:53:41

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> set = new HashSet<Integer>();
        int t = sc.nextInt();

        while (t > 0) {
            set.clear();
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] nums = new int[100050];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
                set.add(nums[i]);
            }

            int a = -1;
            boolean count = false;
            if (k != 0) {
                Arrays.sort(nums, 0, n );
                for (int i = 0; i < n; i++) {
                    if (nums[i] > i) {
                        a = i;
                        count = true;
                        break;
                    }
                }
                
                if(!count){
                    a = n;
                }
                
                if (a < nums[n - 1] ) {
                    int index = (int) Math.ceil((double) (a + nums[n - 1]) / 2);
                    set.add(index);
                    System.out.println(set.size());
                } else  {
                    System.out.println(set.size() + k);
                } 
            }else {
                System.out.println(set.size());
            }
            t--;
        }
    }
}

C++(clang++11) 解法, 执行用时: 60ms, 内存消耗: 3600K, 提交时间: 2021-04-23 12:46:06

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int ss;
	cin>>ss;
	for(int cv=0;cv<ss;cv++)
	{
		int n,k;
		cin>>n>>k;
		vector<long long> x(n);
		set<long long> s;
		long long ma=-1;
		for(int i=0;i<n;i++)
		{
			cin>>x[i];
			s.insert(x[i]);
			ma=max(ma,x[i]);
		}
		long long now=0;
		for(;s.find(now)!=s.end();now++);
		if(now>ma||k==0)
		cout<<s.size()+k<<endl;
		else
		{
			int t=now+ma;
			if(t%2==0)
			t/=2;
			else
			t=t/2+1;
			s.insert(t);
			cout<<s.size()<<endl; 
		 } 
		 s.clear();
	}
	return 0;
}

详情