MENU

C++STL中set的使用策略(二)

March 10, 2018 • Read: 513 • c/c++

看一道 PAT 上的题用set完美解决

题目链接:列车调度

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,k,n,x;
    set<int> s;//定义一个名为s的集合
    while(cin>>n)
    {
        for(int i = 0;i < n;i++)
        {
            cin>>x;
            if(s.empty())//判断集合s是否是空集
            {
                s.insert(x);//是的话向集合s插入一个元素x
            }
            else
            {
                set<int>::iterator it;//定义一个set型的迭代器
                it = s.lower_bound(x);//进行二分查找
                if(it == s.end())
                {
                    s.insert(x);//插入一个元素x
                }
                else
                {
                    s.erase(it);//删除指定元素it
                    s.insert(x);//插入一个元素x
                }
            }
        }
        int t = s.size();//集合s的大小
        cout<<t<<endl;
    }
    return 0;
}

蒜头君的随机数

蒜头君想在学校中请一些同学一起做一项问卷调查,为了确保实验的客观性,他先用计算机生成了 n(1≤n≤100) 个 1 到 1000 之间的随机整数,对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。
请你协助蒜头君完成 “去重” 与“排序”的工作。

输入格式

共两行,第一行为一个正整数 n。
第二行有 n 个用空格隔开的正整数,为所产生的随机数。

输出格式

第一行输出一个正整数 m,表示不相同的随机数的个数。第二行输出 m 个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

样例输入

10
20 40 32 67 40 20 89 300 400 15

样例输出

8
15 20 32 40 67 89 300 400

代码

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
       set<int> q;
       int n,x;
       int sum = 0;;
       cin>>n;
       while(n--)
       {
              cin>>x;
              q.insert(x);
       }
       cout<<q.size()<<endl;
       set<int>::iterator it;
       for(it = q.begin();it != q.end();it++)
       {
              sum++;
              if(sum != q.size())
              {
                  cout<<*it<<" ";
           }
           else
           {
                  cout<<*it;
           }
       }
      
       return 0;
}
Archives Tip
QR Code for this page
Tipping QR Code