【解题报告】洛谷P7726 天体探测仪

思路

对于排列中的一个数字 ii ，设以 ii 为区间最小值的最长的区间是 [li,ri][l_i,r_i]

首先考虑：如果已知 li,ril_i,r_i ，如何求出来 ii 的具体位置

设 leni=ri−li+1len_i=r_i-l_i+1 则对于某个 j≤lenij \le len_i 这段区间里面就一共有 leni−j+1len_i-j+1 个长度为 jj 的子区间，如果所有长度为 jj 的区间中都包括 ii ，那么 ii 在 SjS_j 中就应该出现了 leni−j+1len_i-j+1 次，反之，它在这个集合中的出现次数小于 leni−j+1len_i-j+1 次

因此，我们可以找到最大的 jj 使得 ii 在 SjS_j 中出现的次数 ≤leni−j+1\le len_i-j+1 次，那么 ii 到区间边界的距离就是 jj ,也就是说，ii 到区间边界的距离就应该是 jj ，也就是说, ii 的位置就是 li+jl_i+j 或者 ri−jr_i-j

这两个位置是等价的，因为区间整体反转一下也不会对答案产生影响

我们发现上面的分析中只用到了 lenilen_i ，而 li,ril_i,r_i 仅仅用来定位，所以我们只要设法求出 lenilen_i 就可以了

而 lenilen_i 就是使得 i∈Ski \in S_k 最大的 kk ，容易求出

实现的时候，我们首先求出来 lenilen_i 和 ii 在以它为最小值的区间中的位置，然后从小到大扫描一个 ii ，每次将 ii 放到一个长度为 lenilen_i 的没有用的区间中

考虑如何维护这个闲置的区间呢？

用一堆队列来维护所有长度为 ii 的闲置区间的左端点，一开始的时候只有 1∈qn1 \in q_n 每次确定一个数字之后就会将一个闲置的区间分成两部分

时间复杂度 O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=805;
int n,k;
int a[maxn];
int seg[maxn][maxn];
queue <int> q[maxn];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n-i+1;j++)
		{
			int x;
			cin>>x;
			seg[i][x]++;
		}
	}
	q[n].push(1);
	for(int x=1;x<=n;x++)//枚举选择的数字 
	{
		int len=0;
		for(int i=n;i>=1;i--)
		{
			if(seg[i][x]>0)
			{
				len=i;//找到一个长度为i的区间存在x 
				break;
			}
		}
		int k=0;
		for(int j=1;j<=len;j++)
		{
			if(seg[j][x]==len-j+1)//看是否在某个区间的长度里面在所有的区间里面出现了 
			{
				k=j-1;//找到一个小于使得这个这个区间的长度 
				break;
			}
		}
		int l=q[len].front();//长度为len的可以放置的下一个区间的最小坐标 
		q[len].pop();//取出第一个数字 
		a[l+k]=x;//
		if(k>0)//如果k的区间长度大于1的话 
		q[k].push(l); //把这个东西放回去
		if(len-k-1>0)//如果减去这个之后的区间长度大于1 
		q[len-k-1].push(l+k+1);//那么更改放的位置，我们新的坐标改成这个 
	}
	for(int i=1;i<=n;i++)
	cout<<a[i]<<" ";
	cout<<'\n';
	return 0;
}