Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!
The only thing Mrs. Smith remembered was that any permutation of nn can be a secret phone number. Only those permutations that minimize secret value might be the phone of her husband.
The sequence of nn integers is called a permutation if it contains all integers from 11 to nn exactly once.
The secret value of a phone number is defined as the sum of the length of the longest increasing subsequence (LIS) and length of the longest decreasing subsequence (LDS).
A subsequence ai1,ai2,…,aikai1,ai2,…,aik where 1≤i1<i2<…<ik≤n1≤i1<i2<…<ik≤n is called increasing if ai1<ai2<ai3<…<aikai1<ai2<ai3<…<aik. If ai1>ai2>ai3>…>aikai1>ai2>ai3>…>aik, a subsequence is called decreasing. An increasing/decreasing subsequence is called longest if it has maximum length among all increasing/decreasing subsequences.
For example, if there is a permutation [6,4,1,7,2,3,5][6,4,1,7,2,3,5], LIS of this permutation will be [1,2,3,5][1,2,3,5], so the length of LIS is equal to 44. LDS can be [6,4,1][6,4,1], [6,4,2][6,4,2], or [6,4,3][6,4,3], so the length of LDS is 33.
Note, the lengths of LIS and LDS can be different.
So please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of LIS and LDS.
The only line contains one integer nn (1≤n≤1051≤n≤105) — the length of permutation that you need to build.
Print a permutation that gives a minimum sum of lengths of LIS and LDS.
If there are multiple answers, print any.
4
3 4 1 2
2
2 1
In the first sample, you can build a permutation [3,4,1,2][3,4,1,2]. LIS is [3,4][3,4] (or [1,2][1,2]), so the length of LIS is equal to 22. LDS can be ony of [3,1][3,1], [4,2][4,2], [3,2][3,2], or [4,1][4,1]. The length of LDS is also equal to 22. The sum is equal to 44. Note that [3,4,1,2][3,4,1,2] is not the only permutation that is valid.
In the second sample, you can build a permutation [2,1][2,1]. LIS is [1][1] (or [2][2]), so the length of LIS is equal to 11. LDS is [2,1][2,1], so the length of LDS is equal to 22. The sum is equal to 33. Note that permutation [1,2][1,2] is also valid.
#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define N 100009 #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) int n,a[N]; /* 分成x组，每一组y个，x*y==n,求x+y的最小值，很明显x==sqrt(n)时成立 当n%sqrt(n)==0时，令m=n/sqrt(n)，即x*m==n 那么分成x组：LDS==x，每一组里的数升序，总体递减 每一组m个： LIS==m 每一组x个 ：LDS=x 分成y组 ： LIS=m 当n%sqrt!=0 时，就是再将剩下的放到另一组里 */ int main() { scanf("%d",&n); int index=sqrt(n);//每一组index个 int tmp=1,t; for(int i=n-index;i>=0;i-=index){ t=i; for(int j=0;j<index;j++){ a[i+j]=tmp++; } } for(int i=0;i<t;i++) a[i]=tmp++;//剩下的再放到另一个组里 for(int i=0;i<n;i++){ printf("%d%c",a[i],i==n-1?‘\n‘:‘ ‘); } return 0; }
原文：https://www.cnblogs.com/tingtin/p/9457984.html