363045841 的博客

Appearance

这题增加了数据规模，所以要用堆实现一个选择排序时 O(nlogn) 的最小值搜索

STL priority_queue ​

这玩意很神奇，传入由小到大，是一个大根堆，反之则是一个小根堆，反直觉对吧。

cpp
struct less : public binary_function<_Tp, _Tp, bool>
{
    _GLIBCXX14_CONSTEXPR
    bool
    operator()(const _Tp &__x, const _Tp &__y) const
    {
        return __x < __y;
    }
};//STL实现

在优先队列建堆的时候会使用 less 函数判断根节点和子节点的大小关系，如果值为 true，进行交换操作。 正常情况下如果父节点小于子节点，把大的子节点交换上去，那就是大根堆，重载<运算符，令其结果为 __x > __y，也就是父节点比子节点大的话，交换上去，自然构建的是一个小根堆。 根本原因是因为 less 函数是这么定义的，所以会反直觉一下，重载影响的是交换过程，而不是直观上的大小根堆。^[关于优先队列priority_queue大小根堆、重载操作符的说明_superhuanghai的技术博客_51CTO博客]

使用优先队列降低查找区间最小值的时间复杂度 ​

这个算法的实质是将选择排序的最小值的可能值放到优先队列中，借助优先队列的小根堆特性来找到子区间的最小值，然后模拟一个元素交换过程。

维护可能值 ​

  1. 读入数据的时候，所有数据都需要被搜索，因此全部入队，都是可能值
  2. 每次取出最小元素，确认这个元素是在被搜索的区间内（也就是选择排序的 [i,size]），把这个元素交换到前面去，然后把前面的元素交换到后面去。如果不在搜索区间内，说明这个元素记录的所在位置已经是有序的了，选择这个元素不合法，需要丢弃，看下面的 dbg 数据可以看出来：
1
6
8 83 79 1 87 51
[debuging.cpp:56] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 8 83 79 1 87 51
[debuging.cpp:64] (t.v,t.cur): 1 3
[debuging.cpp:73] (h.size()): 6
[debuging.cpp:74] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 1 83 79 8 87 51
[debuging.cpp:64] (t.v,t.cur): 8 0
[debuging.cpp:64] (t.v,t.cur): 8 3
[debuging.cpp:73] (h.size()): 5
[debuging.cpp:74] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 1 8 79 83 87 51
[debuging.cpp:64] (t.v,t.cur): 51 5
[debuging.cpp:73] (h.size()): 5
[debuging.cpp:74] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 1 8 51 83 87 79
[debuging.cpp:64] (t.v,t.cur): 79 2
[debuging.cpp:64] (t.v,t.cur): 79 5
[debuging.cpp:73] (h.size()): 4
[debuging.cpp:74] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 1 8 51 79 87 83
[debuging.cpp:64] (t.v,t.cur): 83 1
[debuging.cpp:64] (t.v,t.cur): 83 3
[debuging.cpp:64] (t.v,t.cur): 83 5
[debuging.cpp:73] (h.size()): 2
[debuging.cpp:74] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 1 8 51 79 83 87
[debuging.cpp:64] (t.v,t.cur): 87 4
[debuging.cpp:64] (t.v,t.cur): 87 5
[debuging.cpp:73] (h.size()): 1
[debuging.cpp:74] (num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first): 1 8 51 79 83 87
Stable

除了第一次外，其余因为节点被交换过，但是交换前的节点不一定是最小值而被出队，所以会在队列中存在非法的残留元素，需要排除掉。

元素交换 ​

从队列中弄出后面区间的最小值后还要把数据在 num 数组中交换回去，即将第 i 项设置为后面交换的那一项，num 数组记录一个节点的值和其原始所在位置。注意交换到后面的那个位置应该用队列元素的 cur 来确定实时的位置。

屎山，带调试宏和一些调试语句：

cpp
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct item
{
    int v;
    int pos;
    int cur;

    friend bool operator<(const item &a, const item &b)
    {
        if (a.v != b.v)
        {
            return a.v > b.v;
        }
        return a.cur > b.cur;
    }
};

bool solve()
{
    int x;
    cin >> x;
    using pil = pair<int, int>;
    vector<pil> num(x);
    priority_queue<item> h;
    for (int i = 0; i < x; i++)
    {
        cin >> num[i].first;
        num[i].second = i;
        h.push({num[i].first, i, i});
    }
    dbg(num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first);

    for (int i = 0; i < x; i++)
    {
        do
        {
            auto t = h.top();
            h.pop();
            dbg(t.v,t.cur);

            if (t.cur >= i)
            {                                                 // 如果在后面的搜索区间内
                h.push({num[i].first, num[i].second, t.cur}); // 模拟一个swap(t,num[i])
                pil tmp = num[i];
                num[i].first = t.v;
                num[i].second = t.pos;
                num[t.cur] = tmp;
                dbg(h.size());
                dbg(num[0].first,num[1].first,num[2].first,num[3].first,num[4].first,num[5].first);
                break; // 找到了，退出
            }

        } while (true);
    }
    return is_sorted(num.begin(), num.end());
}
int main(int argc, char const *argv[])
{
/* #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif */
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cout << (solve() ? "Stable" : "Unstable") << endl;
    }

    return 0;
}

对拍数据生成：

cpp
#include <bits/stdc++.h>
using namespace std;
int generateRandomNumber(int min, int max)
{
    std::random_device rd;                         // 用于获取随机数种子
    std::mt19937 gen(rd());                        // 以 rd() 作为种子初始化 Mersenne Twister 生成器
    std::uniform_int_distribution<> dis(min, max); // 定义分布
    return dis(gen);                               // 生成并返回随机数
}
int main(int argc, char const *argv[])
{
    freopen("input.txt", "w", stdout);
    int n;
    cin >> n;
    cout << n << endl;
    vector<int> v;
    
    for (int i = 0; i < n; i++)
    {
        int num_of_v = generateRandomNumber(1, 10);
        cout << num_of_v << endl;
        v.clear();
        for (int i = 0; i < num_of_v; i++)
        {
            int num = generateRandomNumber(1, 100);
            v.push_back(num);
        }
        shuffle(v.begin(), v.end(), default_random_engine());
        for (auto i : v)
        {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}