学习随笔——codeforces题目Build Permutation解答

摘要：本题属于构造算法，虽然简单但对思维提升有一定帮助

题目原地址如下：https://codeforces.com/problemset/problem/1713/C

题目截图如下：

 关键词：构造算法，动态规划，*1200

简要翻译：给定一个序列a[0,1,2，.....,n-1]，求其排列A[a1,a2,...an-1]使得对任意ai满足ai+i为完全平方数。

 作为构造题，我们需要考察其内在结构，对n=18的情况，我们会发现从8至17的数字只需让其排列倒转即可实现完全平方的要求。也即我们可以根据完全平方数将原序列划分为多个区域，对每个区域进行考察即可。

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 int n,input;
 4 int edge;//记录边界，当需要改变完全平方数时就需要变更边界，即所得数不可大于该边界 
 5 int rem[10000],a[100005];
 6 int main(){
 7     for (int i=0;i<=1000;i++){//获取完全平方数 
 8         rem[i]=i*i;    
 9     }
10     cin>>n;
11     while(n){
12         cin>>input;
13         int i=0;
14         edge=input-1;
15         for (;rem[i]<=2*input-2;i++);//确定初始的完全平方数 
16         i--;
17         for (int j=input-1;j>=0;j--){//从后向前遍历，便于更新边界 
18             while (rem[i]-j>edge){//边界与完全平方数的更新 
19                 edge=j;
20                 i--;
21             }
22             if (rem[i]-j<=edge)//倒转操作 
23                 a[j]=rem[i]-j;
24         }
25         for (int k=0;k<=input-1;k++)
26             cout<<a[k]<<" ";
27         cout<<"\n";
28         n--;
29     }
30     return 0;
31 }