PAT 排序

满分

/**
难点:模拟置换排序

需要仔细读题的: 只要比弹出的数大即可,因为这样就能使序列是递增的

用10万的数组就内存超限了......

两个指针, count控制整体的while循环, idx控制是否有数要插入heap和vector中
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    int m, k;
    cin >> m >> k;
    vector<int> p(m);
    for(int i = 0; i < m; i++) cin >> p[i];

    priority_queue<int, vector<int>, greater<>> heap;
    vector<int> outp, next;
    // 这一步模拟非常难,必须要理解清楚
    int idx = 0, count = 0;
    for(; idx < k; idx++) heap.push(p[idx]);

    while (count != m)
    {
        int last = heap.top();
        heap.pop();
        outp.push_back(last);
        count++;
        if (idx < m)
        {
            if (p[idx] > last) heap.push(p[idx]);
            else next.push_back(p[idx]);
            idx++;
        }
        if (heap.empty())
        {
            bool flag = true;
            for(int i = 0; i < outp.size(); i++)
            {
                if (flag) flag = false;
                else printf(" ");
                printf("%d", outp[i]);
            }
            outp.clear();
            printf("\n");
            for(int i = 0; i < next.size(); i++) heap.push(next[i]);
            next.clear();
        }
    }
}

方法二: 17分 三个段错误

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 100010;
int q[N];

int main()
{
    int m, k;
    cin >> m >> k;
    for(int i = 0; i < m; i++) cin >> q[i];
    priority_queue<int, vector<int>, greater<int>> heap;
    int min_n = -1;
    int cnt = 0;
    for(int i = 0; i < k; i++)
    {
        heap.push(q[i]);
        cnt++;
        if (q[i] > min_n) min_n = q[i];
    }
    bool flag = true;
    vector<int> res;
    while (heap.size())
    {
        int x = q[cnt++];

        int it = heap.top();
        min_n = it; // 核心就是这个min_n 取值,就可以免去排序了
        if (flag) flag = false;
        else printf(" ");
        printf("%d", it);
        heap.pop();
        if (cnt <= m)
        {
            if (x > min_n)
            {
                //min_n = x;
                heap.push(x);
            }else res.push_back(x);
        }

        if (heap.size() == 0)
        {
            printf("\n");
            flag = true;
            min_n = -1;
            for(int j = 0; j < res.size(); j++)
            {
                heap.push(res[j]);
                if (res[j] > min_n) min_n = res[j];
            }
            res.clear();
        }
    }
}

方法一 17分, 三个段错误

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 10010;
int a[N];
int main()
{
    int m, k ,i, min_s = -1;
    cin >> m >> k;
    for(i = 0; i < m; i++) cin >> a[i];

    // 每K位排序一次,输出block
    priority_queue<int, vector<int>, greater<int>> heap;

    // 先排序
    for(i = 0; i < m; i += k)
    {
        int len = min (m, i + k);
        sort(a + i, a + len);
    }
    for(i = 0; i < k; i++)
    {
        heap.push(a[i]);
        if (a[i] > min_s) min_s = a[i];
    }
    //for(int i = 0; i < m; i++)
    vector<int> vc;
    bool flag = true;
    while (heap.size())
    {
        auto it = heap.top();
        heap.pop();
        if (flag) flag = false;
        else printf(" ");
        printf("%d", it);
        if (i < m)
        {
            if (a[i] > min_s) heap.push(a[i++]);
            else vc.push_back(a[i++]);
        }

        if (heap.size() == 0)
        {
            flag = true;
            printf("\n");
            min_s = -1;
            for(int j = 0; j < vc.size(); j++)
            {
                heap.push(vc[j]);
                if (vc[j] > min_s) min_s = vc[j];

            }
            vc.clear();
        }

    }
}