题解 P7427 【[THUPC2017] 玩游戏】

luckydrawbox · 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;
}