2024/1/21 集合（set,迭代器，map）

目录

不重复数字

木材仓库（迭代器）

学籍管理（map）

不重复数字

P4305 [JLOI2011] 不重复数字 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题用stl里面的set，让数组去重，最后输出就行了，记得开long long ，不然会爆int

注意：a[k++]=x是先赋值再返回，所以最后遍历数组的时候（从1开始），是<k而不是<=k

注意一下下标就可以了

for(int i = 1;i < k;i ++)
        {
            std::cout<<a[i]<<" ";
        }

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 5e4+10;
int a[N];
int x;
signed main()
{
    int t;
    std::cin >> t;
    while(t --)
    {
        std::set<int>s;
        int n;
        std::cin >> n;
        int k = 1;
        for(int i = 1;i <= n;i ++)
        {
            std::cin >> x;
            if(s.find(x)==s.end())
            {
                a[k++]=x;
                s.insert(x);
            }
            else
                continue;
        }
        //std::cout<<k<<"\n";
        for(int i = 1;i < k;i ++)
        {
            std::cout<<a[i]<<" ";
        }
        std::cout<<"\n";
        x=0;
    }
    return 0;
}

木材仓库（迭代器）

P5250 【深基17.例5】木材仓库 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：使用迭代器auto,查找>=x的第一个元素的下标。

分三种情况讨论：

1 ：如果迭代器返回的是第一个位置（auto it==s.begin()） 那说明仓库里面全部是比这个木头大的木头，此时输出第一个位置的元素（不用++）并且清空这个数

2：如果迭代器返回的是最后一个位置（auro it==s.end()）那说明仓库里面全部是比这个木头小的木头，此时输出最后一个位置的元素（需要--）并且清空这个数

3：如果迭代器返回的位置在中间，那么需要比较短木头和长木头与输入的木头的差，谁更小就输出这个木头的长度并且清空这个数

完整代码：

#include <bits/stdc++.h>
#define int long long
signed main()
{
    int n;
    std::cin >> n;
    std::set<int> s;
    for(int i = 1;i <= n;i ++)
    {
        int op,x;
        std::cin >> op >> x;
        if(op==1)
        {
            if(s.find(x)==s.end())
            {
                s.insert(x);
            }
            else if(s.find(x)!=s.end())
            {
                std::cout<<"Already Exist\n";
            }
        }
        else if(op==2)
        {
            if(s.empty())
            {
                std::cout<<"Empty\n";
                continue;
            }
            else
            {
                if (s.find(x) != s.end())//找到了
                {
                    std::cout << x << "\n";
                    s.erase(x);
                    continue;
                }
                else if (s.find(x) == s.end())
                {
                    auto it=s.upper_bound(x);//返回第一个>x的数
                    if (it == s.end())
                    {
                        std::cout << *std::prev(it) << "\n";
                        s.erase(std::prev(it));
                        continue;
                    }
                    if(it==s.begin())
                    {
                        std::cout<<*it<<"\n";
                        s.erase(it);
                        continue;
                    }
                    if(it!=s.end()&&it!=s.begin())
                    {
                        auto it1=std::prev(it);
                        auto it2=it++;
                        if(x-*it1<=*it2-x)
                        {
                            std::cout<<*it1<<"\n";
                            s.erase(it1);
                            continue;
                        }
                        else if(x-*it1>*it2-x)
                        {
                            std::cout<<*it2<<"\n";
                            s.erase(it2);
                            continue;
                        }
                    }
                }
            }

        }
    }
    return 0;
}

学籍管理（map）

P5266 【深基17.例6】学籍管理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题用map

map的一些操作：

mp.find(name) == mp.end()//查找name是否在map里面，这个是不存在
mp.size()//输出map的个数
mp.erase(name)//删除map中的这个name

完整代码：

#include <bits/stdc++.h>
#define int long long
signed main() {
    int n;
    std::cin >> n;
    std::map<std::string, int> mp;
    for (int i = 1; i <= n; i++) {
        int op, score;
        std::string name;
        std::cin >> op;
        if (op == 1) {
            std::cin >>name >> score;
            if (mp.find(name) == mp.end())//没有找到
            {
                mp[name] = score;
                std::cout << "OK\n";
                continue;
            } else if (mp.find(name) != mp.end()) {
                mp[name] = score;
                std::cout<<"OK\n";
                continue;
            }
        }
        if (op == 2) {
            std::cin >> name;
            if (mp.find(name) == mp.end()) {
                std::cout << "Not found\n";
            } else {
                std::cout << mp[name] << "\n";
                continue;
            }
        }
        if (op == 3) {
            std::cin >> name;
            if (mp.find(name) == mp.end()) {
                std::cout << "Not found\n";
                continue;
            } else {
                mp.erase(name);
                std::cout<<"Deleted successfully\n";
                continue;
            }
        }
        if (op == 4) {
            std::cout<<mp.size()<<"\n";
        }
    }
    return 0;
}