Go to Luogu to read my blog
Ideas
We need to try to minimize the maximum value minus the minimum value of the sum of two adjacent numbers.
First think about how to minimize the maximum value.
for
n
n
n, minimum must be placed on both sides
1
1
1 and
2
2
2. So the maximum value is at least
n
+
2
n+2
n+2.
At the same time, let us think again
1
1
1 What can be placed around? Because the minimum value cannot be too small, we need to put something larger, that is
n
n
n and
n
?
1
n-1
n?1.
Looking at it this way, the minimum and maximum value is
n
n
n.
So except
n
=
1
n=1
n=1 or
n
=
2
n=2
Except for the special case of n=2, the minimum value of the sequence we want to construct is
2
2
2.
Let’s think about whether it can be achieved
2
2
2. For greater than
?
n
2
?
\lceil\frac n 2\rceil
?2n’s
i
i
i, his sides can be placed
n
?
i
+
2
n-i+2
n?i + 2 and
n
?
i
+
1
n-i+1
n?i+1. For less than
?
n
2
?
\lfloor \frac n 2\rfloor
?2n’s
i
i
i, his sides can be placed
n
?
i
+
1
n-i+1
n?i + 1 and
n
?
i
n-i
n?i. You can verify that it is placed like this and then process it.
n
n
In the special case where n is an even number, the value can be
2
2
2.
So, we’re thinking about how to generate sequences.
First of all, it can be determined
n
n
n position, put on both sides of it
1
1
1 and
2
2
2. Again
1
1
1 Place the empty space next to it
n
?
1
n-1
n?1, in
2
2
2 Place the empty space next to it
n
?
2
?
n-2 \cdots
n?2?.
It can be found that this construction method can be described in another way.
Put one first
n
n
n, then add numbers on both sides each time, no.
2
×
k
?
1
2\times k-1
2×k?1 addends are added on both sides
2
×
k
?
1
2\times k-1
2×k?1 and
2
×
k
2\times k
2×k,th
2
×
k
2\times k
2×k addends are added on both sides
n
?
2
×
k
+
1
n-2\times k + 1
n?2×k + 1 and
n
?
2
×
k
n-2\times k
n?2×k.
If there is only one left in the end, that is
n
n
When n is an even number, the remaining numbers can be placed at either end.
AC code
#include<bits/stdc + + .h>
using namespace std;
int n,a,b[1000005],now,cnt=1,mi,ma,ha;
int main()
{<!-- -->
scanf("%d", & amp;n),now=n,mi=1,ma=n-1,ha=ceil(1.0*n/2),b[ha]=n;//Too lazy to count every What number is placed next, so I use two variables to store it, and ha records the position in the middle.
while(cnt<=(n-1)/2)
if(cnt &1) b[ha-cnt]=mi,b[ha + cnt]=mi + 1,mi + =2, + + cnt;
else b[ha-cnt]=ma,b[ha + cnt]=ma-1,ma-=2, + + cnt;//Place the numbers according to the above method
if(n%2==0) b[n]=mi;//Situation when n is an even number
for(int i=1;i<=n; + + i) printf("%d ",b[i]);//output
return 0;
}