CodeForces 622D Optimal Number Permutation

时间:2022-08-10 17:04:12

是一个简单构造题。

请观察公式:

CodeForces 622D Optimal Number Permutation

绝对值里面的就是 |di-(n-i)|,即di与(n-i)的差值的绝对值。

事实上,对于任何n,我们都可以构造出来每一个i的di与(n-i)的差值为0。

换句话说,就是这个最小值一定可以构造出来是0。

假设输入是6:
那么可以这样构造:1 3 5 5 3 1 2 4 6 4 2 6

假设输入是7:
那么可以这样构造:1 3 5 7 5 3 1 2 4 6 6 4 2 7

从上面就能看出怎么构造了,n最后放空缺的两个位置,剩下的从小到大一个一个放,奇数放左边构造,偶数放右边构造。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std; const int maxn = * + ;
int n;
int ans[maxn]; int main()
{
scanf("%d", &n);
memset(ans, , sizeof ans);
int left = , right = n + ;
for (int i = ; i <= n - ; i++)
{
if (i % == )
{
ans[left] = i;
ans[left + n - i] = i;
left++;
}
else
{
ans[right] = i;
ans[right + n - i] = i;
right++;
}
}
for (int i = ; i <=* n; i++) if (!ans[i]) ans[i] = n;
for (int i = ; i <= *n; i++) printf("%d ", ans[i]);
printf("\n");
return ;
}