FZU - 2260 Card Game （单调栈）

你的名字 2021-03-30 15:46 427阅读 0赞

有如下取牌游戏：

1. 桌面上有n张卡牌从左到右排成一行，每张卡牌上有一个数字；

2. 游戏按轮次进行，每一轮中取掉所有比左边数值小的卡牌；

3. 当无牌可取的时候则游戏结束。

比如初始卡牌为\{5, 6, 3, 7, 4, 1, 2\}，共需2轮取牌。取牌过程如下（小括号为每轮取掉的牌）：

\{5, 6, 3, 7, 4, 1, 2\}

==> \{5, 6, (3), 7, (4), (1), 2\}

==> \{5, 6, 7, 2\}

==> \{5, 6, 7, (2)\}

==> \{5, 6, 7\}

现按顺序给定初始的卡牌数字，请求出游戏结束时取牌的总轮次，并输出结束时桌上剩余的卡牌序列。

Input

包含多组测试数据。

输入包含两行。

第一行包含一个整数n表示卡牌的数量。

第二行包含n个空格隔开的整数，表示排成一行的卡牌上对应的数字(取值范围\[1,1000000000\])。

n≤1000000

Output

输出包含两行。

第一行包含一个整数表示游戏的取牌总轮次。

第二行包含游戏结束时桌上剩余的卡牌序列，用空格隔开。

Sample Input

7
    5 6 3 7 4 1 2

Sample Output

2
    5 6 7

用一个递增的栈a存最后剩下的元素，遇到大于等于a[top]的元素就入a栈，否则入b栈；栈b存a[i]和a[i-1]间会被拿

出的牌；

最大的问题在于如何求游戏的轮数，观察一下不难发现每张牌被抽出的轮数=该牌往前数几张牌才能遇到大于自己的牌；

但是要是真这样去做很容易wa或者tle(来自开始这样写，然后改了四个小时的怨念)；嗯~ o(*￣▽￣*)o正题来了：

用b来模拟抽牌，只不过不是像真正的游戏那样一轮一轮地抽，而是把a[i]和a[i-1]间的某区间牌先抽完，再继续处理后面

的，具体操作看代码；每次取最大的轮数。（轮数等于往前走遇到第一个大于该牌的区间中最大的轮数加一(因为要左边的牌

比自己大才会被抽走，所以要遇到比自己大的数之前的牌都被抽走，它才能被抽走)）

a:  63        b:  2             c:1            //c存轮数

a:  63        b:  56            c:2

a:  63        b:  56  3         c:2 1

a:  63        b:  57            c:3

a:  63        b:  57  9         c:3 1

a:  63        b:  57  10        c:3 2

a:  63        b:  57  11        c:3 3

a:  63        b:  58            c:4

a:  63        b:  58  6         c:4 1

a:  63        b:  58  6  5      c:4 1 1

a:  63        b:  58  20        c:4 2
`
    #include<cstdio>
    #define MAXX 1000050
    
    
    int a[MAXX];
    int b[MAXX];   //单调栈
    int c[MAXX];     //记录b[0]~b[topb]间牌被抽走的轮数
    int main()
    {
    	int n;
    	while (scanf("%d", &n) != EOF)
    	{
    		int topa = -1;
    		int topb = -1;
    		int x;
    		int max = 0;
    		for (int i = 0; i < n; i++)
    		{
    			scanf("%d", &x);
    			if (topa == -1)
    			{
    				topa++;
    				a[topa] = x;
    			}
    			else if (a[topa] <= x)
    			{
    				topa++;
    				a[topa] = x;
    				topb = -1;
    			}
    			else
    			{
    				if (topb == -1)
    				{
    					topb++;
    					b[topb] = x;
    					c[topb] = 1;
    				}
    				else if (x < b[topb])
    				{
    					topb++;
    					b[topb] = x;
    					c[topb] = 1;
    				}
    				else if (x >= b[topb])
    				{
    					int t=-1; while (topb>-1&&x >= b[topb]) { if(c[topb]>t) t=c[topb]; topb--; } b[++topb] = x; c[topb] = t+1;
    					if (c[topb] > max)max = c[topb];
    				}
    				if (c[topb] > max)max = c[topb];
    			}
    
    		}
    		printf("%d\n", max);
    		int flag = 1;
    		for (int i = 0; i <= topa; i++)
    		{
    			if (flag)flag = 0;
    			else printf(" ");
    			printf("%d", a[i]);
    		}
    		if(!flag)printf("\n");
    	}
    }