产生冠军（集合set）

港控/mmm° 2023-07-16 03:56 24阅读 0赞

### 集合set ###

*   *  关于集合set的学习：
     *   *   *  集合定义
             *  关于set我有话说：
             *  用数组初始化集合：
             *  访问：
             *  遍历：
     *  题目：
     *  我的代码：
     *   *   *  解一：
             *  解二

## 关于集合set的学习： ##

#### 集合定义 ####

> 之所以称为集合，就是因为set与数学中的集合一样，存在互异性，也就是每一个元素只允许出现一次。set的特性是：所有元素都会根据元素的键值自动排序，set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值，实值就是键值。set不允许两个元素有相同的键值。

**set** 中的元素已从小到大排好序，用一个 for循环即可从小到大遍历所有的元素。  
而**map** 就是从键（key）到值（value）的映射。  
因为重载了 \[ \] 运算符，使其可以像数组一样使用，map也称为 “关联数组”。

#### 关于set我有话说： ####

1.  对于关联容器来说，不需要做内存拷贝和内存移动。所以map和set的插入删除效率比用其他序列容器高。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。所以删除，插入都是类似于链表的指针改变指向。
2.  begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.
3.  equal\_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。
4.  set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等

struct Info
            {
        
                string name;
                float score;
                //重载“<”操作符，自定义排序规则
                bool operator < (const Info &a) const
                {
        
                    //按score从大到小排列
                    return a.score<score;
                }
            }
            set<Info> s;
            ......
            set<Info>::iterator it;

关于map：[map1][]  
[map2][]

#### 用数组初始化集合： ####

#inlcude <set>
    set<T> a; //T为各种数据类型
    T src[20];
    set<T>b(src,src+sizeof(src)/sizeof(*T));/
    /利用已有数据源初始化集合a，两个形参分别是初始数据的开始地址以及结束地址

#### 访问： ####

> set 的成员函数 find() 会返回一个和参数匹配的元素的迭代器。如果对象不在 set 中，会返回一个结束迭代器。  
> 调用成员函数 count() 可以返回指定键所对应的元素个数，返回值通常是 0 或 1，因为 set 容器中的元素是唯一的。

#### 遍历： ####

迭代器：

set<int>::iterator iter;
        for(iter=a.begin();iter!=a.end();iter++)
        {
        
            cout<<*iter<<endl;
        }

反向迭代器：

set<int>::reverse_iterator riter;
        for(riter=a.rbegin();riter!=a.rend();riter++)
        {
        
            cout<<*riter<<endl;
        }

常用函数：

1.  **begin()**–返回指向第一个元素的迭代器
2.  **clear()**–清除所有元素
3.  **count()**–返回某个值元素的个数
4.  **empty()**–如果集合为空，返回true
5.  **end()**–返回指向最后一个元素的迭代器
6.  **equal\_range()**–返回集合中与给定值相等的上下限的两个迭代器
7.  **erase()**–删除集合中的元素 a.erase(val);//删除键值val
8.  **find()**–返回一个指向被查找到元素的迭代器，没找到则返回end
9.  **get\_allocator()**–返回集合的分配器
10. **insert()**–在集合中插入元素  
    **a.insert(pos,val)**;//在pos位置添加值val，**位置不重要**，因为插入后，set会自动排序
11. **lower\_bound()**–返回指向大于（或等于）某值的第一个元素的迭代器
12. **key\_comp()**–返回一个用于元素间值比较的函数
13. **max\_size()**–返回集合能容纳的元素的最大限值  
    例如set a; a.max\_size返回的就是整型的上界214748364
14. **rbegin()**–返回指向集合中最后一个元素的反向迭代器
15. **rend()**–返回指向集合中第一个元素的反向迭代器
16. **size()**–集合中元素的数目
17. **swap()**–交换两个集合变量
18. **upper\_bound()**–返回大于某个值元素的迭代器
19. **value\_comp()**–返回一个用于比较元素间的值的函数

## 题目： ##

产生冠军  
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 29670 Accepted Submission(s): 13310

Problem Description  
有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。  
球赛的规则如下：  
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。  
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。  
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

Input  
输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。

Output  
对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。

Sample Input  
3  
Alice Bob  
Smith John  
Alice Smith  
5  
a c  
c d  
d e  
b e  
a d  
0

Sample Output  
Yes  
No

## 我的代码： ##

#### 解一： ####

\*\*拓扑图：\*\*输了比赛则入度加一。比如a跟b比赛，a赢了b，则a指向b，b的入度就加1。最后判断入度为0的是否只有一个，如果只有一个，就可以产生冠军，输出“Yes”,否则，就产生不了冠军，输出“No”。由于涉及到一个人可能参加多场比赛，且胜负不定，因此要给每一个参加比赛的人设置一个特有的编号，因此需要是要到map容器来使运动员的名字和编号对应起来，然后通过一个数组来记录运动员输了的比赛数量

#include <iostream>
    #include<vector>
    #include<map>//要使用map，必须包含此头文件
    #include<string>
    #include<queue>
    using namespace std;
    
    map<string,int> M;//定义完成从string到int映射的map
    int in[2002];
    int main()
    {
        
        int n;
        while(scanf("%d",&n)!=EOF){
        
            for(int i=0;i<2*n;i++)//n组胜负关系，至多存在n个队伍
                in[i]=0;//初始化入度
            M.clear();//清空一个map
            int idx=0;//下一个被映射的数字
            for(int i=0;i<n;i++){
        
                char str1[50],str2[50];
                scanf("%s%s",str1,str2);
                string a=str1,b=str2;
                int idxa,idxb;
                if(M.find(a)==M.end()){
        //map中没有对a的映射
                    idxa=idx;
                    M[a]=idx;//设定其映射为idx
                    idx++;//递增idx
                }
                else
                    idxa=M[a];//直接读出该映射
                if(M.find(b)==M.end()){
        
                    idxb=idx;
                    M[b]=idx;
                    idx++;
                }
                else
                    idxb=M[b];
                in[idxb]++;//b的入度递增
            }
            int cnt=0;
            for(int i=0;i<idx;i++){
        //统计入度为0的个数
                if(in[i]==0)
                    cnt++;
            }
            puts(cnt==1?"YES":"NO");//入度为0的点唯一说明有冠军
        }
        return 0;
    }

#### 解二 ####

列表set的去重性可以很好的解决这题：  
定义集合A,B，把所有人放进集合A，把我所有有失败记录的放进集合B，则A-B如果等于1，则能产生冠军；否则不能。

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        
        set< string >A, B;  //定义集合
        string s1, s2;
        int n;
        while(cin>>n && n){
          //n=0时输入结束
            for(int i=0; i<n; i++){
        
                cin>>s1>>s2;
                A.insert(s1);
                A.insert(s2);  //所有人放进集合A
                B.insert(s2);  //失败者放进集合B
            }
            if(A.size() - B.size() == 1)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
            A.clear();
            B.clear();
        }
        return 0;
    }

[map1]: https://blog.csdn.net/weixin_42324771/article/details/88082882
[map2]: https://www.cnblogs.com/fnlingnzb-learner/p/5833051.html