侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【栈】双向排序【蓝桥杯】

GabrielxD
2023-01-17 / 0 评论 / 0 点赞 / 52 阅读 / 894 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

3419. 双向排序 - AcWing题库

双向排序 - 蓝桥云课


给定序列 (a1,a2,,an)=(1,2,,n)(a_1, a_2, ··· , a_n) = (1, 2, · · · , n) ,即 ai=ia_i = i

小蓝将对这个序列进行 mm 次操作,每次可能是将 a1,a2,,aqia_1, a_2, ··· , a_{q_i} 降序排列,或者将 aqi,aqi+1,,ana_{q_i}, a_{q_i+1}, ··· , a_n 升序排列。

请求出操作完成后的序列。

输入格式

输入的第一行包含两个整数 n,mn, m ,分别表示序列的长度和操作次数。

接下来 mm 行描述对序列的操作,其中第 ii 行包含两个整数 pi,qip_i, q_i 表示操作类型和参数。当 pi=0p_i = 0 时,表示将 a1,a2,,aqia_1, a_2, ··· , a_{q_i} 降序排列;当 pi=1p_i = 1 时,表示将 aqi,aqi+1,,ana_{q_i}, a_{q_i+1}, ··· , a_n 升序排列。

输出格式

输出一行,包含 nn 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。

数据范围

对于 30%30\% 的评测用例, n,m1000n, m ≤ 1000
对于 60%60\% 的评测用例, n,m5000n, m ≤ 5000
对于所有评测用例, 1n,m1050pi11qin1 ≤ n, m ≤ 10^5,0 ≤ p_i ≤ 1,1 ≤ q_i ≤ n

输入样例:

3 3
0 3
1 2
0 2

输出样例:

3 1 2

样例解释

原数列为 (1,2,3)(1, 2, 3)

11 步后为 (3,2,1)(3, 2, 1)

22 步后为 (3,1,2)(3, 1, 2)

33 步后为 (3,1,2)(3, 1, 2) 。与第 22 步操作后相同,因为前两个数已经是降序了。

解题

方法一:栈

思路

y总的视频讲解:AcWing 3419. 双向排序(蓝桥杯C++ AB组辅导课)

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<int[]> stk = new ArrayList<>();
        while (m-- > 0) {
            in.nextToken();
            int p = (int) in.nval;
            in.nextToken();
            int q = (int) in.nval;
            if (p == 0) {
                while (!stk.isEmpty() && stk.get(stk.size() - 1)[0] == 0) q = Math.max(q, stk.remove(stk.size() - 1)[1]);
                while (stk.size() >= 2 && stk.get(stk.size() - 2)[1] <= q) {
                    stk.remove(stk.size() - 1);
                    stk.remove(stk.size() - 1);
                }
                stk.add(new int[]{0, q});
            } else if (!stk.isEmpty()) {
                while (!stk.isEmpty() && stk.get(stk.size() - 1)[0] == 1) q = Math.min(q, stk.remove(stk.size() - 1)[1]);
                while (stk.size() >= 2 && stk.get(stk.size() - 2)[1] >= q) {
                    stk.remove(stk.size() - 1);
                    stk.remove(stk.size() - 1);
                }
                stk.add(new int[]{1, q});
            }
        }
        int l = 1, r = n, k = n;
        int[] ans = new int[n + 1];
        for (int[] pr : stk) {
            if (pr[0] == 0) {
                while (r > pr[1] && l <= r) ans[r--] = k--; 
            } else {
                while (l < pr[1] && l <= r) ans[l++] = k--;
            }
            if (l > r) break;
        }
        if ((stk.size() & 1) == 0) {
            while (l <= r) ans[r--] = k--;
        } else {
            while (l <= r) ans[l++] = k--;
        }
        for (int i = 1; i <= n; ++i) {
            System.out.print(ans[i] + " ");
        }
    }
}
0

评论区