思路是这样的:
设 sum1=1+2+⋯+2N,
设 sum2=(2N+1)+(2N)+⋯+N
首先,如果 A+B>sum1+sum2 或者 max(A,B)>sum2,无解。
之后,令 i∈[1,N],ai=i。
之后,从两端开始,对于数 ai 和 aN−i+1,如果两者调换位置后 sum2 依旧大于等于 B,那么交换,直到 sum1 大于等于 A。(见代码加星号部分)
个人分析:每次交换相当于给 sum2 减一个奇数,给 sum1 加一个同样的奇数,比如:
a={1,2,3,4,5,6}
交换 a1,a6,则 sum2 加上 5,sum1 减去 5;
交换 a2,a6,则 sum2 加上 3,sum1 减去 3 ;
交换 a1,a6,则 sum2 加上 5 ,sum1 减去 1 ;
我发现,若干个从 1 开始的连续奇数,假如有 K 个,则它们可以组成 [0,K2] 之间的所有数,但不能组成 2 和 K2−2。 因此特判这两种情况,其它的都可以被组成。
时间复杂度为严格的 O(N)。
我自认为逻辑没什么问题,也通过了所有测试点,如果有人能够证伪或给出 hack 数据,或者给出严谨的正确性证明,非常感谢o(〃^▽^〃)o
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
long long A,B;
long long sum1,sum2;
int N,T;
int a[MAXN];
signed main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&N);
sum1=0,sum2=0;
for(int i=1;i<=N;i++)
{
a[i]=i;
if(i<=N/2) sum1+=i;
else sum2+=i;
}
scanf("%lld %lld",&A,&B);
if(A+B>sum1+sum2||max(A,B)>sum2) puts("-1");//判无解
else if(A+B==sum1+sum2&&(abs(sum1-A)==2||abs(sum2-A)==2)) //特判!
{
if(abs(sum1-A)==2)
{
swap(a[N/2-1],a[N/2+1]);
}
else
{
for(int i=1;i<=N/2;i++) swap(a[i],a[N-i+1]);
swap(a[N/2-1],a[N/2+1]);
}
for(int i=1;i<=N;i++) printf("%lld ",a[i]);
puts("");
}
else//***************************
{
bool flag=0;
for(int i=1;i<=N/2;i++)
{
if(sum1>=A&&sum2>=B)
{
flag=1;
break;
}
if(sum2-a[N-i+1]+a[i]>=B)
{
sum2=sum2-a[N-i+1]+a[i];
sum1=sum1-a[i]+a[N-i+1];
// printf("%lld %lld\n",sum1,sum2);
swap(a[i],a[N-i+1]);
if(sum1>=A&&sum2>=B) flag=1;
}
}
if(flag==0) printf("-1");
else for(int i=1;i<=N;i++) printf("%lld ",a[i]);
puts("");
}/*******************
}
return 0;
}