题目链接：https://codeforces.ml/gym/102875/problem/C

题意：每只猫的高度为1~20  两只同样高度的猫中间的最矮的猫不能比他们高

用1~20构造出这样的序列

思路  按  1 然后2个空位插2    1 2 1    4个空位插3 变为  3 1 3 2 3 1 3即可  最多构造2^20-1>1e5

直接用dfs 分区间搞即可   其实也是二叉树的中序遍历

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define pb push_back
 5 const int mod=1e4;
 6 const int maxn=1e6+10;
 7 int ans[maxn];
 8 
 9 
10 
11 void dfs(int l,int r,int x)
12 {
13     int mid=(l+r)/2;
14     ans[mid]=x;
15     if(l<=mid-1) dfs(l,mid-1,x+1);
16     if(r>mid) dfs(mid+1,r,x+1);
17 }
18 
19 int main()
20 {
21     ios::sync_with_stdio(0);
22     cin.tie(0);
23     int n;
24     cin>>n;
25     dfs(1,n,1);
26     for(int i=1;i<=n;i++)
27     {
28         if(i!=1)
29             cout<<" ";
30         cout<<ans[i];
31     }
32     cout<<'\n';
33 
34 
35 
36 
37 
38 
39 }

View Code