自动搬运

查看原文

来自洛谷，原作者为

	luckydrawbox **

搬运于2025-08-24 22:29:47，当前版本为作者最后更新于2021-03-19 20:32:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

分析

易得 ljcc 和学妹的总得分必定为 $1+2+3+……+n$，由小学学过的等差数列求和可得总得分为 $\tfrac{n(n+1)}{2}=a+b$，如何求 $n$ 呢？

即 n=sqrt(2*(a+b))。

我们求出 $n$ 后，判断 $n(n+1)$ 是否与 $2(a+b)$ 相等。

• 若不相等，说明无解，直接输出 No，结束程序。

• 若相等，说明有解，输出 $n$，接下来开始构造：

构造的想法与P7071 [CSP-J2020] 优秀的拆分的贪心相似，枚举 $i$ 从 $n$ 到 $1$，若 $a≥i$，则令 a-=i，并输出 $i$，即尽量减去较大的得分，可以用决策包容性证明这个贪心是正确的。

当然，你会注意到 $a,b$ 的最大值为 $2^{31}−1$，加起来一定会超过 int 范围，所以要开 long long。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,n;//long long莫忘 
int main()
{
    cin>>a>>b;
    n=sqrt(2*(a+b));//求n 
    if(n*(n+1)!=2*(a+b))//判断是否相等 
    {
    	//无解 
    	cout<<"No";
    	return 0;
	}
	//有解 
	cout<<n;
    for(int i=n;a;i--)//从n开始向下枚举 
    {
    	if(a>=i)
    	{
    		a-=i;//尽量减大的 
    		cout<<" "<<i;//注意格式 
		}
	}
	return 0;
}