这是一道通过贪心进行构造的题目来着，写完以后呃呃呃其实我不是很会分析这题的复杂度来着，所以准备贴一下朋友让 gemini 帮忙分析的复杂度
先看思路吧：
用一个数组 来存储一个数在不超过
的情况下，最多有几个数是它的整倍数
用一个数组 来存储一个
内的数是否已经在构造中被使用
随后我们来检查原数列 是否能构造出合法排列，
这里我们要满足两个条件：
条件1：前一项必须是后一项的倍数，因为 
只会变得越来越小,且前项除以后项一定要无余数
条件2：现在的个数i必须小于等于 
范围内是 
的倍数的数的数量，因为由条件1，前面几项也一定都得是 的倍数
满足以上 2 个条件时，我们就能构造出题目要求的 排列
接下来开始我们的构造:
当 时，可以中断，因为这个时候只要从小到大按顺序输出未被
标记的元素即可（按顺序第一个输出的一定是
，而由于前缀
，所以只要现在这个
是
，后面的数填什么都无所谓）
当 时,我们贪心地选择未被标记过的
的最大倍数作为
的答案，这样一定是最优的
然后gemini 帮忙分析的复杂度分析如下：（唉latex什么的写得真好看但我真不会写啊）
该解答程序的时间复杂度为 O(n log² n)（最坏情况）。具体分析如下：
1. 整体结构
代码主要分为四个部分：
- 读入并初始化
cnt数组：cnt[i] = n / i - 合法性检查（前缀整除关系等）
- 贪心构造前
i个元素（当a[i] > 1时） - 补全未被使用的数字（
vis[i] == false的部分）
其中初始化和合法性检查均为 O(n)。
2. 贪心循环的复杂度
for (ll i = 2; i <= n; i++) {
if (a[i] > 1) {
while (vis[cnt[a[i]] * a[i]] || gcd(cnt[a[i]] * a[i], a[i - 1]) != a[i])
cnt[a[i]]--;
// 输出并标记
} else break;
}
关键在于内层 while 循环的总执行次数。
-
cnt[x]的初值是⌊n / x⌋，且只会递减，递减到 0 为止。 -
对于所有不同的
x = a[i]，cnt[x]减少的总次数不会超过其初值之和：这里
x=1不会进入该循环（遇到a[i]==1直接break）。
因此，所有 while 循环的迭代次数总和为 O(n log n)。
3. 每次迭代的代价
while 循环中执行：
vis[...]数组访问 —— O(1)gcd(cnt[a[i]] * a[i], a[i-1])计算 —— 数据范围 ≤ n，欧几里得算法复杂度 O(log n)- 递减
cnt[a[i]]—— O(1)
由于 || 短路特性，当 vis 已为真时不计算 gcd；但在最坏情况下，可能每次都要计算 gcd，因此单次迭代代价上界为 O(log n)。
综合总代价：O(n log n) × O(log n) = O(n log² n)。
4. 其余部分
- 最后的补全循环遍历
1..n输出未使用的数，O(n)。 - 空间复杂度主要由
a, vis, cnt三个长度为n+1的数组组成，为 O(n)。
结论
该程序在理论最坏情况下的时间复杂度为 O(n log² n)，对于题目限制 完全可以接受。实际运行中，由于
cnt 的快速下降以及 vis 的提前拦截，常数很小。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 100;
const double EPS = 1e-8;
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n;
vector<ll> a(n + 1), vis(n + 1), cnt(n + 1);
for (ll i = 1; i <= n; i++)
cin >> a[i];
for (ll i = 1; i <= n; i++)
cnt[i] = n / i;
for (ll i = 2; i <= n; i++)
{
if (a[i - 1] % a[i] != 0 || n / a[i] < i) // 先判断是否合法
{ // 条件1：前一项必须是后一项的倍数
cout << -1 << endl; // 条件2：现在的个数i必须小于等于[1,n]范围内是a[i]的倍数的数的数量
return;
}
}
cout << a[1] << ' ';
vis[a[1]] = 1;
for (ll i = 2; i <= n; i++)
{
if (a[i] > 1)
{
while (vis[cnt[a[i]] * a[i]] || gcd(cnt[a[i]] * a[i], a[i - 1]) != a[i])
cnt[a[i]]--;
cout << cnt[a[i]] * a[i] << ' ';
vis[cnt[a[i]] * a[i]] = 1;
}
else
break;
}
for (ll i = 1; i <= n; i++)
{
if (!vis[i])
cout << i << ' ';
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
// cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号