序列整理

视频题解点击此处查看

题目阅读

题目讲述了AC狗遇到一个问题，给一个无序序列，序列是从1~N，在输出某个数a的时候需要去他前面找比他大的数k，如果有就输出在一起。如果没有满足的k的话就只输出这个数a。

题意抽象

给你一个无序序列，里面的数值是1_{N，然后让你按照顺序输出1}N，但是每要输出一个数的时候就要去找这个数值前面下标比他小的数，在这些下标小于当前选中数值下标的数当中，查找是否有数值更大的数，如果有，则将这些数字按照顺序输出在同一行，如果没有，则这个数单独占一行。

算法分析

本题模拟下查找操作即可，此处仅介绍其一种思路。

​ 因该序列必然是1~N不重复数字的序列，我们可以开辟一个数组Vis，记录数字出现的位置。例: 在于6次输入中输入数字 3 ,那么Vis[3] = 6 ,我们以输入的数值作为数组的下标，记录数字出现的位置。 同时我们可以设定一个 it 作为输出数值的标记，代表我们当前处于输出第几个数值。由于输出的规律必然为 1~N 输出，那么it是一个单调递增+1的标记。我们每输入一个数的时候，就判断 Vis[it] 是否有被标记过位置，如果有，则输出当前的数值it，同时查找it+1是否又被标记过，如果被标记过，那么it+1的出现的地方必然在it前，将其合并，一直查找到没有被标记过的数值在停下。

代码

#include <iostream>
#include <cstring>

using namespace std;

int vis[510000]; // 设定标记数值出现下标的数组

int main()
{
 int n;
 memset(vis, -1, sizeof(vis)) ;// 初始化数组状态
 cin >> n;
 int it = 1;
 for (int i = 1; i <= n; i++)
 {
  int t;
  cin >> t; 
  vis[t] = i; // 将输入数值作为数组的下标，同时记录该数字出现的位置
  if (it == t) // 如果当前数值等于要输出的数值时输出
  {
   cout << it;  
   it++;
   while ((vis[it] != -1) && (it <= n)) // 查找在这个数字之前是否有大于他相邻的数字出现。
   {
    cout << "," << it;
    it++;
   }
   cout << endl;
  }
 }
 return 0;
}