the sound of sea
剪枝操作真是让我这个思考片面，做事潦草的人震惊了
#include #include #define LOCAL using namespace std; /* 先计算出每个数的个数（1e5*1e5太大了，用map--map中的元素是自动按照key升序排列，并且不能再用sort） 然后从小到大每找到一个a就利用该a和前面所有a将大于1的区间和对应的数-1，那么下一个还存在的数便是下一个a 核心思想： 反向思考和递推思想，将除了（干扰）下一个结果的所有值利用前面的排除，而且可以完全排除掉，这样就可以找到下一个结果了 起死回生之术了吧： 剪枝操作：在一开始就将所有大于1e5的数全部排除！！！！！！！！！！！！！！！ */ typedef long long ll; const ll maxn=2010; map num; ll rs[maxn];// from 1_index ll read(){ ll s=0,c=getchar(),f=1; while (c<'0' || c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0' && c<='9') {s=(s<<3)+(s<<1)+c-'0';c=getchar();} return f*s; } int main(){ #ifdef LOCAL freopen("input.txt","r",stdin); #endif ll n=read(); ll tmps=n*(n+1)/2; for (ll i=0;i1e5) continue; num[tmp]++; } ll cont=0; for (map::iterator it=num.begin();it!=num.end();++it){ while (it->second){ rs[++cont]=it->first;// a1 --> rs[1] ll tmp=0; for (ll i=cont;i;--i){ tmp+=rs[i]; if (tmp>1e5) break; num[tmp]--; } } } for (ll i=1;i<=cont;++i) printf("%lld ",rs[i]); return 0; }