20161007 NOIP 模拟赛 T1 解题报告

排序

3.1 题意描述

众所周知，熟练掌握至少一种排序算法是参加NOIP的必备技能。常见的排序算法有冒泡排序、归并排序、快速排序、奇偶排序、猴子排序、梳排序、鸡尾酒排序、臭皮匠排序等。在这里，介绍一种利用栈进行排序的方法。例如，当数组中的元素为 1，3，2 时，我们可以利用栈对其进行排序：1 入栈；3 入栈；3 出栈；2 入栈；2 出栈；1 出栈。在这个例子中，出栈序列是 3，2，1，因而实现了对数组的排序。遗憾的是，在不打乱入栈顺序的前提下，有时仅仅借助一个栈是不能实现对数组的完全排序。例如给定数组 2，1，3，借助一个栈，能获得的字典序最大的出栈序列是 3，1，2。（2 入栈；1 入栈；3 入栈；3 出栈；1 出栈；2 出栈）现请你借助一个栈，在不打乱入栈顺序的情况下，对数组进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。

3.2 输入格式

输入共 2 行。第一行包含一个正整数 n，表示入栈序列长度。第二行包含 n 个整数，表示入栈序列。输入数据保证给定的序列是 1 到 n 的全排列，即不会出现重复数字。
3.3 输出格式
输出仅一行，共 n 个整数，表示字典序最大的出栈序列。

3.4 样例输入

5 2 1 5 3 4

3.5 样例输出

5 4 3 1 2

3.6样例解释

2 入栈；1 入栈；5 入栈；5 出栈；3 入栈；4 入栈；4 出栈；3 出栈；1 出栈；2 出栈

3.7 数据规模与约定

• 对于 40% 的数据：N ≤ 10；

• 另有 20% 的数据：N ≤ 103；

• 另有 20% 的数据：N ≤ 105；

• 对于 100% 的数据：N ≤ 106。

————————————————分割线————————————————

分析：

1.1 题意简述
给定一个栈和一个 n 的全排列作为入栈序列，试通过调整出栈次序，得到字典序最大的出栈序列。

1.2 解法一
暴力枚举每次是入栈还是出栈，即穷举所有可能的出栈序列，从而得到字典序最大的出栈序列。时间复杂度：O(C(n))，其中 C(n) 为卡特兰数列的第 n 项，期望得分 40 分。

1.3 解法二
使用各种神奇的贪心算法，求解字典序最大的出栈序列。由算法复杂度及正确性决定最后得分。期望得分 0−100 分。

1.4 解法三

依旧考虑贪心算法。要求字典序最大，故我们可以从 n 到 1 贪心地试探每个数能否加入出栈序列。假设我们已经枚举到了 i，若栈顶元素比 i 大，我们则可以弹出栈顶元素，将其加入出栈序列，直到栈顶元素≤ i。若 i 未在栈中，我们则将入栈序列中在 i 前面且未入栈的数入栈，并将 i 加入出栈序列；若 i 在栈中且是栈顶元素，我们则将 i 弹出栈，并加入出栈序列；若 i 已经在栈中且不是栈顶元素，则说明若将 i 加入出栈序列，之前必然要把比 i 小的数弹出栈，我们不这样做，继续枚举 i−1。注意由于涉及大规模文件处理，此题需要使用输入输出优化。时间复杂度为 O(n)，期望得分 100 分。

本蒟蒻考试时写了解法二，得了55分。现在看来，出数据的人特别善良，我的完全乱搞的蜜汁算法居然给了55分！！

算了还是贴上错误代码。

#include "cstdio"
#include "cstring"
#include "algorithm"
#include "iostream"
#define Never return 
#define Explode 0 

using namespace std ;
const int maxN = 10e6 + 100 ;
const int INF = 2147483647 ;

int stack[ maxN ] , arr[ maxN ] ;

int top ;

inline int gmax ( int x , int y ) {return x > y ? x : y ; }

int INPUT ( ) {
        int x = 0 , f = 1 ;char ch = getchar( ) ;
        while ( ch < '0' || ch > '9' ) { if( ch == '-' ) f= -1 ; ch = getchar( ) ; }
        while ( ch >= '0' && ch <= '9' ) { x = ( x << 1 ) + ( x << 3) + ch - '0' ; ch = getchar( ) ; }
        return x * f ;
}

int main ( ) {
        freopen ( "sort.in" , "r" , stdin ) ;
        freopen ( "sort.out" , "w" , stdout ) ;
        int N = INPUT ( ) ;
        int M = N ;
        for ( int i=1 ; i<=N ; ++i ) {
                stack[ ++ top  ] = INPUT ( ) ;
                while ( stack [ top ] == M && top ) {
                        printf ( "%d " , stack[ top-- ] ) ;
                        --M ;
                }
        }
        while ( top ) printf ( "%d " , stack[ top-- ] ) ;
        fclose ( stdin ) ;
        fclose ( stdout ) ;
        Never Explode ;
}

贴上AC代码：

 1 #include "bits/stdc++.h"
 2 #define Never return
 3 #define Explode 0
 4 
 5 using namespace std ;
 6 const int maxN = 10e6 + 100 ;
 7 
 8 int stk[ maxN ] ;
 9 int vis[ maxN ] ;
10 
11 int top ;
12 
13 int INPUT ( ) {
14         int x = 0 , f = 1 ;char ch = getchar( ) ;
15         while ( ch < '0' || ch > '9' ) { if( ch == '-' ) f= -1 ; ch = getchar( ) ; }
16         while ( ch >= '0' && ch <= '9' ) { x = ( x << 1 ) + ( x << 3) + ch - '0' ; ch = getchar( ) ; }
17         return x * f ;
18 }
19 
20 int main ( ) {
21         int N = INPUT ( ) ;
22         int M = N ;
23         freopen ( "hahaha.out" , "w" , stdout ) ;
24         for ( int i=1 ; i<=N ; ++i ) {
25                 int tmp = INPUT( ) ;
26                 while ( vis[ M ] ) -- M ; //还未入栈的期望的最大值 
27                 while ( M < stk[ top ] ) {
28                         printf ( "%d " , stk[ top -- ] ) ;
29                 }
30                 
31                 if ( tmp == M ) printf ( "%d " , tmp ) , vis[ tmp ] = true ;
32                 else {
33                         stk[ ++top ] = tmp ;
34                         vis[ tmp ] = true ;
35                 }
36         } 
37         while ( top > 0 )printf ( "%d " , stk[ top -- ] ) ;
38         Never Explode ;
39 }

AC++

NOIP_RP++;

2016-10-07 23:29:49

(完)