题解：P7726 天体探测仪（Astral Detector）

· · 题解

一、对称

假设数组有7个元素，先放数字 1，1 放到第 1 个位置和放到第 7 个位置的作用是一样的；放到第 2 个位置和放到第 6 个位置的作用是一样的，放到第 3 个位置和第 5 个位置的作用是一样的。

对于 7 个元素的数组，数字 1 可以有 4 个位置可以放。

二、确定1的位置

假设将 1 放在下标 1 的位置，则长度为 4 的区间最小值只会有 1 个 1，假设将 1 放在下标 2 的位置，则长度为4的区间最小值会有 2 个 1 ，假设将 1 放在下标 3 的位置，则长度为 4 的区间最小值会有 3 个 1 ，假设将 1 放在下标 4 的位置，则长度为 4 的区间最小值会有 4 个 1。

根据长度为4的区间最小值1的个数就能确定1的位置。

如果区间总长度为 len ，则根据长度为 (len+1)\div2 的区间最小值 1 的个数就能确定 1 的位置

三、确定2的位置

数字 1 插入后，这个时候被分为了两个区间，接下来考虑数字 2 的插入，将数字 2 插入到一个区间，同上述数字1 插入一个区间的过程是一样的。

假设数字 1 被放入了位置 1 ，根据长度为 3 的区间最小值 2 的个数就能确定数字 2 在区间中的位置。

由于区间有很多个，不能确定放在哪个区间，所以需要将每个区间循环一次，找到一个插入。

后面数字 3 到 n 的插入都是一样的。

四、很多个区间，到底插入到哪一个

假设数字 x 应该插入的区间长度为 len ，则长度为 len+1 的区间最小值不会是 x ，因为区间往左或往右长度 +1，区间最小值就会变成之前已经插入的比 x 小的数。

也就是说如果一个区间的长度为 len，存在长度为 len 的区间最小值为 x ，不存在长度为 len+1 的区间最小值为 x ，则 x 可以插入到这个区间。

代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int id,next;  //lian[i].id:数字i放的位置    lian[i].next：数字i后面放的数字编号
}lian[1000005]; //链表。
int f[1005][1005]; //f[i][j]:长度为i的区间最小值(S[i])出现了几次j。 
int main(){
    int n,i,j,a,len;
    cin>>n;
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            cin>>a; 
            f[i][a]++;   //长度为i的区间最小值为a的个数++
        }
    }
    //一开始只有1个[1,n]的区间，区间是通过端点来表示的,设置0的位置被用了，n+1的位置被用了,中间的[1,n]放
    lian[0].next=n+1;
    lian[0].id=0;
    lian[n+1].id=n+1; 
    for(i=1;i<=n;i++){                //依次插入1~n 
        for(j=0;j<=n;j=lian[j].next){ //循环每个区间的起点，终点就是next 
            len=lian[lian[j].next].id-lian[j].id-1; //区间长度，两个点之间的区间还没放过
            //存在长度为len的区间最小值为i，不存在长度为len+1的区间最小值为i
            if(f[len+1][i]==0&&f[len][i]!=0){
                //这个区间从now.id+1开始的,放在区间的第f[(len+1)/2][i]的位置
                //对应的是now.id+1 + f[(len+1)/2][i] -1，加1和减1抵消掉
                lian[i].id=lian[j].id+f[(len+1)/2][i];
                lian[i].next=lian[j].next;//链表插入操作
                lian[j].next=i;
                break; //已经找到，不需要再找。因为多个可行区间任选一个。
            }
        }
    }
    for(i=lian[0].next;i<=n;i=lian[i].next){
        cout<<i<<" ";   //输出依次的每个元素
    }
    return 0;
}