codeforces 1017C The Phone Number [分块+贪心]

题目链接

题意：给你一个数n，让你给出一个有n个数的排列，这n个数分别是1到n，求一个最长上升子序列和最长递减子序列的长度和最小的排列。

题解：通过样例1可以看出只要n是某个整数的平方，那么可以将其分为sqrt（n）块，每一块为sqrt（n）个，那么夹杂在
(n-1)^2 和 n^2 的数该如何方块呢，为何方块就是因为如果方块进行排列：那么每个块以内按递增进行排列，块与块之间按递减排列， 块数+我们所规划好的每块所包含的数量，就是我们要求的结果， 即最小长度和，所以进行一个判断:

如果n无法整除，那么根据n的大小分为 (int)sqrt(n)块 或 (int)sqrt(n)+1块， 每一块都有 (int)sqrt(n)+1 个数

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	while(~scanf("%d", &n)) {
		int a = (int)sqrt(n);
		int dls, lis;
		if(a*a == n) {
			dls = a;
			lis = a;
		} else if(a*(a+1) >= n) {
			dls = a;
			lis = a+1;
		} else {
			dls = a+1;
			lis = a+1;
		}
		for(int i=0; i<dls; i++) {
			for(int j=0; j<lis; j++) {
				int x=(dls-i-1)*lis+j;
				if(x<n) {
					printf("%d ",x+1);
				}
			}
		}
		printf("\n");
	}
	return 0;
}