问题 A: 灌水
时间限制: 1 Sec 内存限制: 256 MB Special Judge题目描述
输入
样例输入1：
3 1
样例输出1：
3 1 2
样例输入2：
4 1
样例输出2：
4 3 1 2
样例输入3：
8 17
样例输出3：
6 2 3 1 8 4 5 7
输出
提示
发现有一个小规律，如果最小的放在最大和次大的中间，对答案贡献最大，而把n个点按顺序排放，再用链表优化，之后从最左端找点看应该放在什么位置（就是判断他对答案的贡献），之后修改链表。如果当前x>=当前点的最大贡献，直接放到最右边，如果<判断一下。。直到x==0或跳出循环。若x!=0，cout<<-1即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 1000000
#define ll long long
using namespace std;
ll read()
{
ll sum=0,f=1;char x=getchar();
while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
while(x>='0'&&x<='9'){sum=(sum<<3)+(sum<<1)+x-'0';x=getchar();}
return sum*f;
}
int n,nex[N+5],fro[N+5];
ll x,a[N+5];
int main()
{
n=read();x=read();
if((ll)(n-2)*(n-1)/2<x){cout<<-1<<endl;exit(0);}
for(int i=1;i<=n;i++)
{
nex[i]=i+1;
fro[i]=i-1;
}
nex[n]=0;nex[0]=1;
for(int i=n-2;i>0;i--)
{
if(x>=i)
{
int k=n-i-1;
fro[nex[k]]=fro[k];
nex[fro[k]]=nex[k];
nex[k]=n;
fro[k]=fro[n];
nex[fro[k]]=k;
fro[n]=k;
x-=i;
}
else
{
int k=n-i-1,len=i-x;
int l=n-len;
fro[nex[k]]=fro[k];
nex[fro[k]]=nex[k];
nex[k]=l;
fro[k]=fro[l];
nex[fro[k]]=k;
fro[l]=k;
x=0;
break;
}
if(x==0)break;
}
if(x>0){cout<<-1<<endl;exit(0);}
for(int i=nex[0];i;i=nex[i])printf("%d ",i);
cout<<endl;
}