Description
You are given a permutation p of the set \({1,2,...,N}\). Please construct two sequences of positive integers \(a_1, a_2, ..., a_N\) and \(b_1, b_2, ..., b_N\) satisfying the following conditions:
·\(1≤a_i,b_i≤10^9\) for all \(i\)
·\(a_1<a_2<...<a_N\)
·\(b_1>b_2>...>b_N\)
·\(a_{p_1}+b_{p_1}<a_{p_2}+b_{p_2}<...<a_{p_N}+b_{p_N}\)
Constraints
·\(2≤N≤20,000\)
·\(p\) is a permutation of the set \({1,2,...,N}\)
Solution
注意到a,b分别是递增和递减的,不妨先按照等差数列构造,首先保证\(a_i+b_i\)不变,然后再按照给如的序列p在a序列的基础上减去一个相对较小的值,保证不会改变原有的单调性,这样就改变了\(a_i+b_i\)的单调性
Note
第一次选值的时候选取了20000,由于太大而影响了最总的结果,这里选择N然后令其递减即可
Code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int p[20000 + 10];
int a[20000 + 10], b[20000 + 10];
int main() {
//freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
for (int i = 1; i <= N; i++) cin >> p[i];
for (int i = 1; i <= N; i++) a[i] = i*20001;
for (int i = N; i >= 1; i--) b[N-i+1] = i*20001;
int base = N;
for (int i = 1; i <= N; i++) {
a[p[i]] -= base;
base--;
}
for (int i = 1; i <= N; i++) cout << a[i] << " ";
cout << endl;
for (int i = 1; i <= N; i++) cout << b[i] << " ";
return 0;
}
原文链接: https://www.cnblogs.com/ez4zzw/p/12595815.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/338666
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!