「RHOI-1」夕阳西下几时回 题解
Ecrade_
·
·
题解
我们首先考虑能否构造一个排列达到这个上界。
将所有 $i$ 和 $2i\ (1\le 2i\le n)$ 连边，则我们得到了若干条链。将这些链依次相接即可，即：
$$(1,2,4,8,...),(3,6,12,...),(5,10,20,...),...$$
那如果 $k$ 比这个上界小呢？很简单，将 $(2k+1)\sim n$ 倒序接在 $1$ 后面以达到 “舍去” 这些数的效果，即：
$$(1,n,(n-1),...,(2k+1)),(2,4,8,...),(3,6,12,...),(5,10,20,...),...$$
当然，构造方案并不唯一。
时间复杂度为 $O(\sum n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k;
inline ll read(){
ll s = 0,w = 1;
char ch = getchar();
while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
return s * w;
}
int main(){
t = read();
while (t --){
n = read(),k = read();
if (k > n / 2){puts("No"); continue;}
puts("Yes"),printf("1 ");
for (ll i = n;i >= k * 2 + 1;i -= 1) printf("%lld ",i);
for (ll i = 1;i <= k * 2;i += 2) for (ll j = max(2ll,i);j <= k * 2;j *= 2) printf("%lld ",j);
puts("");
}
return 0;
}
```