NDK 1368 yep的收藏品

问题描述：

 yep有很多收藏品，为的是以后有机会送给它钟爱的女性朋友，每到假期它都会去收集各式  各样的收藏品，面对琳琅满目的收藏品有时候它都不知道如何下手。但为了女生它一般还是  会勇于献出自己的钱包……

 又到了七夕，yep又该开始准备礼物了，礼物当然是从它所有的收藏品中选取，它有很多很  多件收藏品，但其中不乏重复的收藏，女生收到礼物时是不喜欢看见同种礼物的，要不然会  被视为凑数，被发现的后果很严重，yep会被狠狠地X掉。yep的收藏品是以其价值度来区分  的，即同种的收藏的价值度相同，不同的收藏品价值度不同。价值度数字越小表明这个收藏  品越好。

 但是由于yep的懒惰，买好后的收藏品它从没整理过，于是它们都堆在了一个箱子里面，每  次从箱子中只能拿出一件收藏品，而且拿出一件收藏品必须要把堆在它上面的所有收藏品都  捣出来，所有的收藏品都按先后顺序一个一个垒在箱子里面。

 可没等到七夕那天，女生竟然提前拜访！当时yep还没整理出它要送的礼物呢…………当女  生看到那个箱子的时候，她不禁皱起了眉头，她说：“为了惩罚你这个懒蛋，我要对你送我  的礼物再提出要求。首先，你要送我一个收藏品，你必须也要送给我这件收藏品底下紧挨着  的收藏品，除非它是最底下的一个。否则就不能再送我礼物了，因为你只有一次机会；其  次，你要送给我价值度为I的收藏就一定要送给我价值为I-1的收藏品；最后，你必须送给我  尽可能多的收藏品。“

 面对这个情形，yep心急如焚。幸好它平时有记录自己都买了哪些收藏品，根据记录它就可  以选择要送给她的收藏了……

 现在给你它的记录，请你帮它挑选……

数据输入：

 本题目每个测试点有T组数据。

 第一行输入一个T，表示数据组数，对于每组数据：

 接下来T组数据：

 第一行一个整数n，表示yep拥有的收藏品个数；

 第二行n个数，按顺序表示yep的每件收藏品的价值度，第i个读入的收藏品的位置编号为i。  （价值度均不大于N）

结果输出：

 每组数据只有一行。

 如果有解，输出两个数max和ans，用一个空格隔开。

 max表示yep送给女生的收藏品个数；ans表示它送给她的第一件收藏最早的可能的位置编  号。

 如果无解，输出一个0即可。

样例：

 6

 4

 4 3 2 1

 4

 2 1 2 3

 4

 3 3 2 1

 4

 2 1 1 3

 4

 3 2 4 1

 4

 2 1 4 2

4 1

3 2

3 2

2 1

4 1

2 1 

核心思想：

 经过简化之后本题的意思是：在一串数中找出连续的一段K个数，它们恰好组成1~K的一个  排列，输出最大的K以及这个数段第一个数的位置（如果有多个段符合条件，输出最靠前  的）。

 数据的范围为100000，考虑有O(nlogn)或O（n）两种算法时间复杂度。这里采用的是基本  O(n)的算法。

 由于数段要符合1~K的排列，所以不可能出现两个一样的数。用数组b[I]记录当前数字I所在  的位置，即a[b[I]]=I。用一个变量start表示当前数段的第一个数的位置，初始赋成1。从第一  个数开始扫描，当遇到一个以前已经出现的数，即b[a[I]]<>0。此时再继续扫描已经没有意  义，因为已经有重复的数了，必须先处理原来的数，更新最优解，之后删除原来b[a[I]]及之  前的所有数，因为更新最优解后b[a[I]]之前的数（包括它自己）都没有用了。之后把start更  新为b[a[I]]+1（这个b[a[I]]还是原来的数，并没有更新），之后再把b[a[I]]的值更新为I。依次  枚举直到全部扫描完，最后再更新一次。

 之后的问题是如何更新最优解了，用l、r表示当前数段的左坐标和右坐标。首先如果b[1]=0  表示当前数段内没有1，肯定无解；其次，要保证K=r-l+1。于是可以枚举K，数段长度最少  是2，最长是I(当时第一层循环枚举到的数）-start。直到b[K]=0，或者退出循环，如果b[K]在  区间[l,r]之外则更新[l,r]，如果K=r-l+1那么表示此时[l，r]之间恰好是1~r-l+1的排列，更新最  优解，并记录数段起始位置。

 此算法枚举数时间复杂度O(n)，删除数复杂度O(n)，不确定因素唯有第二层循环枚举K的  量，只能因数据而异，但实际上由于如果b[a[I]]=0那么直接更新b[a[I]]而不会进入循环，频繁  进入循环势必不会枚举过多量，枚举很多量要建立在之前很长时间没有进入第二层的循环基  础之上，所以复杂度不会过高，但不排除有使本算法退化成O(n^2)的数据，限于本人数学水  平有限，不会进行严谨的证明，时间分析姑且写到这里。

 空间复杂度O(n)

 题解这么强大绝对不是我写的，而且程序会更强大，各位扶好坐好。