很有意思的构造题,前面尽可能长的设一连串1,后面用[n+1,2n]去补,补的方式也是一连串的构造,使连续串尽可能长,每段的贡献是len*(len-1)/2
#include<bits/stdc++.h> using namespace std; #define N 200005 #define ll long long ll n,m,a[N]; int main(){ int t;cin>>t; while(t--){ cin>>n>>m; for(int i=1;i<=n;i++){ if(m>=n-i){ a[i]=1;m-=n-i; }else {//m<n-i ll len=10000,p=n+1; while(i<=n){ while(len*(len-1)/2>m)len--; for(int j=i;j<=i+len-1;j++) a[j]=p; p++; m-=len*(len-1)/2; i=i+len; } } } for(int i=1;i<=n;i++)cout<<a[i]<<' '; puts(""); } }
原文链接: https://www.cnblogs.com/zsben991126/p/13061894.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/353545
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!