P11277 世界沉睡童话 题解

我有一个更加神仙的做法！

首先，我们知道：放 x 个相同的数能得到 \frac{x(x-1)}{2} 个对。

直接考虑用上面的方式填感觉很乏力。

我们再考虑一个很“强劲”的方式：放 1，这样能直接得到 n-1 个对。

那么考虑先放 1，把 k 减小（ 同时 n-1 ），再放相同的数。

发现有一个很好的性质：放完以后 k<n-1。

然后就可以线性地放，放 3 个相同能得到 3 个，那么我们就先放 3 个相同的。

如果最后 k=1，放一对相同的。

如果最后 k=2，放两对相同的（由于 k<n-1 所以这样做刚刚好放得下）。

最后，为了放相同的数时不会互相干扰，我们依次放 n,n+1,\cdots 2n-1；

#include<bits/stdc++.h>
#define rg register int
#define fo(i,l,r) for(rg i=(l);i<=(r);i++)
#define dfo(i,r,l) for(rg i=(r);i>=(l);i--)
#define fe(i,x) for(rg i=hd[x];i;i=nex[i])
#define frein freopen("in.txt","r",stdin);
#define freout freopen("out.txt","w",stdout);
#define fre(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define outa(l,r,a) {fo(i,l,r)cout<<a[i]<<" ";cout<<"\n";}
#define BZ cout<<"----------------\n";
#define eb emplace_back
#define ll long long
using namespace std;
const int N=3e5+5;ll k;
int tn,n,a[N],p;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;tn=n;
    while(k>=n-1&&k>0){
        k-=n-1;
        a[n--]=1;
    }
    p=n;
    while(k>=3){
        a[n]=a[n-1]=a[n-2]=p++;
        k-=3,n-=3;
    }
    if(k==1)a[n]=a[n-1]=p++,n-=2;
    else if(k==2)a[n]=a[n-1]=p++,n-=2,a[n]=a[n-1]=p++,n-=2;
    fo(i,1,n)a[i]=p++;
    fo(i,1,tn)cout<<a[i]<<" ";
    return 0;
}