山东财经大学新生赛暨天梯赛选拔赛 F 简单排序（队列的基本运用）

秒速五厘米 2022-03-07 08:48 186阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/547/F][https_ac.nowcoder.com_acm_contest_547_F]  
来源：牛客网

## 题目描述 ##

LXK有一个序列，从N~1，但是他不小心把序列打乱了，现在他想找你把这串序列复原。

他讨厌用传统的方式排序。所以他用他自己的方式进行复原。

他有K个先进先出的队列

对于某个数字，你可以选择将其放入任意队列之中（不能不放）。

每个队列中队首的数字可以在任意时间出队列。

利用这些队列，聪明的LXK就可以将序列复原回降序。

他想知道这些操作最少需要准备多少个队列？

## 输入描述: ##

一个数N（N<100000）
    
    表示数字的数目
    
    接下来一行 n个数字

## 输出描述: ##

一个数k
    
    表示最少需要多少个队列才能满足要求

示例1

## 输入 ##

复制

5
    1 2 3 4 5

## 输出 ##

复制

示例2

## 输入 ##

复制

7
    1 2 5 7 3 4 6

## 输出 ##

复制

> 用一个数组来模拟队列。
> 
> 既然是队列操作，那么要进去的数字一定不能比队列里面的数字大。不然小的数字会先出队，就不符合题目 “降序” 的意思了。

#include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    int a[100000+10],b[100000+10];
    int main()
    {
    	int n,m,j,k,i,T;
    	cin>>n;
    	for (i=0;i<n;i++)
    	cin>>a[i];
    	
    	int sum=1;
    	j=0;
    	b[j++]=a[0];
    	for (i=1;i<n;i++)
    	{
    		bool flag=false;
    		for (k=0;k<j;k++)
    		{
    			if (a[i]<=b[k])
    			{
    				b[k]=a[i];
    				flag=true;
    				break;
    			}
    		}
    		if (flag==false)
    		{
    			b[j++] = a[i];
    			sum++;
    		}
    		
    	}
    	cout<<sum<<endl;
    	return 0;
    }

[https_ac.nowcoder.com_acm_contest_547_F]: https://ac.nowcoder.com/acm/contest/547/F