个人任务10.完成一半题目

水深无声 2023-09-28 13:31 5阅读 0赞

作者: Turbo 时间限制: 1S 章节: 课程设计

> **问题描述 :**  
> 有 N 位扣友参加了微软与力扣举办的「以扣会友」线下活动。主办方提供了 2\*N 道题目，整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。  
> 若每位扣友选择不同的一题，请返回被选的 N 道题目至少包含多少种知识点类型。  
> 示例 1：  
> 输入：  
> 4  
> 2 1 6 2  
> 输出：1  
> 解释：共有 2 位扣友，在 4 道题目中选择 2 题。  
> 可选择完成知识点类型为 2 的题目时，此时仅一种知识点类型，因此至少包含 1 种知识点类型。  
> 示例 2：  
> 输入：  
> 12  
> 1 5 1 3 4 5 2 5 3 3 8 6  
> 输出：2  
> 解释：共有 6 位扣友，在 12 道题目中选择题目，需要选择 6 题。  
> 3位选择完成知识点类型为 3 的题目，3位选择完成知识点类型为 5 的题目，因此至少包含 2 种知识点类型.

> **输入说明 :**  
> 输入两行：  
> 第一行为一个整数n代表数组questions的长度，n=2\*N，N为扣友的数量。  
> 第二行输入n个整数代表数组questions的元素。  
> 提示：  
> 2 <= n <= 10^5  
> 1 <= questions\[i\] <= 1000

> **输出说明 :**  
> 输出一个整数表示结果。

> **输入范例 :**  
> 6  
> 1 2 3 4 5 1

> **输出范例 :**  
> 2

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    #include<utility>
    using namespace std;
    int a[100001]={
        0},b[100001]={
        0};//因为n是小于10的5次方，所以a和b数组的范围都应该是10的5次方
    
    int fun(int b[],int n){
        
        int he=0;//用来记录从类型数多向少的个数
        int k=0;//记录有多少种题型
        for(int i=n-1;i>0;--i){
        
            he+=b[i];
            ++k;
            if(he>=(n/2))//如果题目数大于扣友数，则退出循环，返回目前题有多少种类型
                break;
        }
        return k;
    }
    
    int main(){
        
        int n;
        cin>>n;
        for(int i=0;i<n;++i){
        
            cin>>a[i];
            b[a[i]]++;//使用b数组记录每个数出现的次数
        }
        sort(b,b+n);//对数组b排好序
        cout<<fun(b,n)<<endl;
        return 0;
    }