网站 预算,wordpress 标签 彩色,html5手机网站源码下载,网站优化解决方案C - ABS Permutation (LIS ver.)
目录
题意#xff1a;
思路#xff1a;
我没做出来的原因#xff1a; 代码#xff1a; 题意#xff1a;
p数组是permutation#xff0c;n个数#xff0c;所有连续两数之差的绝对值可以构成a数组。问a数组**严格**递增的最长长度是多…C - ABS Permutation (LIS ver.)
目录
题意
思路
我没做出来的原因 代码 题意
p数组是permutationn个数所有连续两数之差的绝对值可以构成a数组。问a数组**严格**递增的最长长度是多少。
x代表p数组首元素。
思路
AtCoder Regular Contest 140 - 知乎
我们先不管首元素是多少。
1 2 3 4 5 6
假如是3的时候可以最大 3 4 2 5 1 6 一右一左 1 2 3 4 5
从 4 开始一左一右相同。n 是奇数最长也是 n-1所以最长长度是 n-1 。 如果不是“中间数”开始的呢我们不管 x 比如是2剩下 1 3 4 5 6 我们对这五个元素进行相同的操作可以得到最长长度为 n - 2.
可以看到虽然2这里跳了多一但是后面的都多一所以a数组仍是严格递增的 我没做出来的原因
没读清楚是严格递增的。
下来自己做也没注意到只有每两个数之间有关系和前面的没有关系所以可以不管x。 代码
注意中间下标的确定我们数组是0开始的。
#includebits/stdc.h
using namespace std;//奇数个存在正中间可以实现 1 ~ n-1
//
////1 2 3 4 5 6
// ^
//1 2 3 4 5
// ^ 就算是2下一个也是3只要不是3起手就是n-2的最大值//
// 1 3 4 5 6
// 0 1 2 3 4const int maxn 2e5 5;
int arr[maxn];
int vis[maxn];
int main()
{int n, x;cin n x;vectorintans;cout x ;for (int i 1; i n; i)if(i ! x)ans.push_back(i);if (n % 2 0 x n / 2)reverse(ans.begin(), ans.end());n--;int aim (n-1) / 2;//n-1)/2就是中或者中偏左for (int i 1; i n; i){cout ans[aim] ;if (i 1)aim i;elseaim - i;}return 0;
}
