題解 P1059 【明明的随機數】

題目連結

本寶寶強烈建議從後往前看

表示set是一個很好用的東西。沒聽說過的可以出門左轉度娘。

set是一個可以去重并且以$O(log n)$的複雜度插入元素，最後我們在找一遍有多少個數就好。直接上set的代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<set>//set需要這個頭檔案。
using namespace std;
set<int> s;//建立集合（set）
set<int>::iterator it;//建立指針
int n,x;//n表示共有幾個數，x表示目前的數
int now;//個數
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        s.insert(x);
    }//輸入，插點
    for(it=s.begin();it!=s.end();it++)//找一遍有多少個數
        now++;
    printf("%d\n",now);//輸出就好
    for(it=s.begin();it!=s.end();it++)
    printf("%d ",*it);
    return 0;//程式百拜拜
}      

好像很懵是吧。（剛才是什麼鬼）

一個簡單一點的方法：拿優先隊列存，入隊列的時候檢查一下有沒有在裡面就好。那怎麼判斷是否在裡面呢？資料範圍這麼小當然是bool數組呀！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>//隊列須要這個頭檔案。
using namespace std;
int n;int x;bool ins[1010];int ans;
/*
n表示輸入幾個數，x還是目前的數，ins[i]表示的是i有沒有在隊列裡，ans是還剩幾個數。
*/
priority_queue<int,vector<int>,greater<int> > q;
//小根堆的優先隊列
int main()
{
      scanf("%d",&n);
      ans=n;//輸入，初始化總共還剩n個數
      for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);//循環輸入
            if(ins[x]==true)
            {
                ans--;//如果這個數之前已經有過了
                continue;//總數-1，跳過
            }
            else
            q.push(x);//否則入隊，标記
            ins[x]=true;
        }
        printf("%d\n",ans);//按題意輸出就好
        for(int i=1;i<=ans;i++)
        {
            printf("%d ",q.top());
            q.pop();
        }
    return 0;
}      

其實資料範圍讓我很欣慰，是以來一個最簡單最暴力的解法，就是直接爆搜。輸入啥就标記，最後搜一遍标記了啥和有幾個數就好

#include<cstdio>
using namespace std;
int n;int x;bool ins[1010];int sum;int ans[1005];
/*
n表示輸入幾個數，x還是目前的數，ins[i]表示的是i有沒有在隊列裡，ans是最後的答案。sum是還剩幾個數
*/
int main()
{
    scanf("%d",&n);//輸入
    for(int i=1;i<=n;i++)
    scanf("%d",&x),ins[x]=true;//直接無腦标記
    for(int i=1;i<=1000;i++)
    if(ins[i]) ans[++sum]=i;
    //按照資料範圍從頭搜一遍就好。在的直接存。
    printf("%d\n",sum);//暴力輸出
    for(int i=1;i<=sum;i++)
    printf("%d ",ans[i]);
    return 0;//程式拜拜
}