1.c++关于set

c++有着丰富的函数以及各种容器，这极大的精简的代码。

题目之外的联想

在看火影第二部的时候，我们都知道，为了节省查克拉的使用，进而产生了一种容器，容器里面装有特定的技能，只要我们发射容器，就会产生和本身技能同样的效果，这不仅节省了查克拉的使用，而且操作简单，每个人都可以使用

c++set容器有着异曲同工之妙

  1. set容器封装了一种非常高效的平衡检索二叉树——红黑树，set中每个元素值都唯一，并且所有的元素都是以节点的方式来存储。因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。
  2. vector封装了数组
  3. list封装了链表
  4. map和set一样。

set中常用的方法

begin() 　　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear() 　　 ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

rbegin　　　　 ,返回的值和end()相同

rend()　　　　 ,返回的值和rbegin()相同

题目描述
现有一堆无聊的木头，它们的长度已知且排成一行，突然有一天，第一块木头突发奇想，它想要知道在它的右边比它长度次小的木头是哪一块，于是
它把这个想法告诉了其他木头，而其他木头对于它这个想法也十分好奇,但是木头实在太多了，因此你需要告诉它们在它们右边的哪一块木头的长度比它次小，也就是找到
比它次小的那块木头的位置。
输入
第一行输入一个T(T <= 20)，表示测试数据组数。
接下来T行，每行首先输入一个n(n <= 100000)，表示木头的个数，之后输入n个正整数，分别表示木头的长度(木头长度<=1000000)
输出
输出n个满足条件的答案，注意如果没有满足条件的答案你只需要输出0就好了，如果对于某块木头有多个满足条件的答案，你需要输出答案尽量小的那一个。
样例输入
1
6 10 9 26 10 10 18
样例输出
2 0 6 0 0 0

题目分析
1.次小——仅次于该高度的高度
2.题目要求在右边寻求次小木头，那我们就反向遍历，依次将木头的高度存入set容器中，也是因为在右边寻找，那么最右边的木头肯定为0,…这样依次下去就简单了许多
3.对于第i个木头用lower_bound函数找到大于等于该木头高度的木头高度h，它的前一个就是次小的木头高度，h已经是第一个，也就意味着没有木头比第i个木头小
4.我们用id数组保存第i个木头的位置
5.我们比较和返回的都是地址，但是在地址的前面加一个*号就代表这个元素的值


AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn], b[maxn], id[maxn];
int main()
{
   
    set<int> s;
    set<int>::iterator it;
    int n, t;
    scanf("%d", &t);
    while (t--)
    {
   
        s.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = n; i >= 1; --i)
        {
   
            s.insert(a[i]);
            it = s.lower_bound(a[i]);
            if (it == s.begin())
                b[i] = 0;
            else
                b[i] = id[*(--it)]; //次小木头的位置
            id[a[i]] = i;           //每个木头对应的位置
        }
        for (int i = 1; i <= n; ++i)
            printf("%d%c", b[i], i == n ? '\n' : ' ');
    }
    return 0;
}
有诗和远方的人，生活不会寂寞