Another Permutation Problem 题解

本文主要是介绍Another Permutation Problem 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

十七、Another Permutation Problem

Another Permutation Problem

根据公式可推出，正序的一定在所有排列中最大，逆序一定最小，证明如下：
注：这里的$i_1，i_2相当于1，2$

对正序排列求取当前元素乘下标：

$i_1^2+i_2^2+...+i_n^2$

对逆序排列求取当前元素乘下标：

$i_1\ast (i_1+n-i_1)+i_2\ast (i_2+(n-i_1)-2^{i_2-1})+...+i_n\ast (i_n+(n-i_1)-2^{i_n-1})$

设$n-i_1=t$

原式$=i_1^2+i_1\ast t+i_2^2+i_2\ast t+...+i_n^2+i_n\ast t-i_1\ast (2^0+2^1+2^2+...+2^n-1)$

整理得到:

$i_1^2+i_2^2+..+i_n^2+(t-2^0)\ast i_1+(t-2^1)\ast i_2+...+(t-2^{n-1})\ast i_n$

$(t-2^0)\ast i_1+(t-2^1)\ast i_2+...+(t-2^{n-1})\ast i_n=t\ast (i_1+i_2+...+i_n)-(2^0+2^2+2^4+...+2^{n-1})$

即比较$\frac{n^3-1}{2}$和$4^{n-1}+1$的大小，显然后者更大，由函数图像直接可以看出，所以：

$(t-2^0)\ast i_1+(t-2^1)\ast i_2+...+(t-2^{n-1})\ast i_n<0$

同样的，正序排列中，任意翻转多个数的位置，会使整体值减小

#include<iostream>
#include<algorithm>
using namespace std;
//证明：逆序一定是最小的，正序一定是最大的（不删减的情况下）
int a[500];
int main(){int t; cin>>t;while(t--){int n; cin>>n;for(int i=1;i<=n;i++){a[i]=i;}int ans=0;for(int len=1;len<=n;len++){int res=0; int tmp=0;for(int i=0;i<=n-len;i++){res+=a[i]*i; tmp=max(tmp,a[i]*i);}for(int i=n-len+1,j=n;i<=n;i++,j--){res+=a[i]*j; tmp=max(tmp,a[i]*j);}res-=tmp;ans=max(ans,res);}cout<<ans<<endl;}
}

这篇关于Another Permutation Problem 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---