题解：CF2117B 缩小操作

# 	缩小操作/Shrink
## 问题描述/Problem
给定从 $1$ 到 $n$ 的 $n$ 个数，要求 $a_{i-1}<a_i<a_{i+1}$ 时可以删除 $a_i$ 。为了尽可能多删除数列中的数，找出一种排列。
## 解决方案/Solution
~~瞪大眼睛~~观察样例，发现删除最后留下的一定是 $1$ 和 $2$ (因为如果剩下的是其他数，必然会有两个比它小的数，因此不是最优解，如 `1 2 3` 。此外，由于没有 $2$ 个数比 $1$ 和 $2$ 小，无法删除，会被保留到最后)。  
所以，我们可以通过倒推的方式找出最优方案的规律。首先，为了让 $a_{i-1}<a_i<a_{i+1}$ 的情况尽可能多。根据贪心，我们可以将最大值放在数列的中央，把最小值放在两侧，例如 `1 3 5 6 4 2` 。
给一个具体的删除过程：
```
1	3	5	6	4	2
1	3	5	-	4	2
1	3	-	-	4	2
1	3	-	-	-	2
1	-	-	-	-	2
```
'-' 代表已被删除的数
## 代码/Code
`-O2 -std=c++11`
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int T;
signed main()
{
	cin>>T;
	for(int t=1;t<=T;t++)
	{
		int n,a[200005];
		memset(a,0,sizeof a);
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			if(i%2==1)
			{
				a[(i+1)/2]=i;
			}
			else
			{
				a[n-(i/2)+1]=i;
			}
		}
		for(int i=1;i<=n;i++) cout<<a[i]<<" ";
		cout<<endl;
	}
	return 0;
}
```
## Other/其他
[codeforces 1029 div2 submission](https://codeforces.com/contest/2117/submission/324005695)  
~~没想到第一篇题解是红题~~  
The End

正在渲染内容...