自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 22:23:57，当前版本为作者最后更新于2020-08-26 23:27:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这里来讲一下 $O(1)$ 的做法。

首先题目上说：造第 $i$ 层楼需要 $i$ 个 A 材料和 B 材料。

所以说，造前 $n$ 层就需要 $\dfrac{n(n+1)}{2}$ 个 A 材料和 B 材料。

先不管我们那 $c$ 元钱，我们先看只有 $a,b$ 时的情况。

题意此时就是让我们求出最大的 $n$，满足 $\dfrac{n(n+1)}{2}\le a,\dfrac{n(n+1)}{2}\le b$。

---

简洁点说，就是解不等式嘛！

这种不等式早就被套路艹烂了，不过这里还是带大家来解一下吧qwq。

$$\begin{aligned} &\dfrac{n(n+1)}{2}&\le &\ a\\ \iff&n(n+1)&\le&\ 2a\\ \iff&n^2+n-2a&\le&\ 0\\ \end{aligned} $$

可以发现此时就只剩一个一元二次不等式了。

那么，直接上求根公式，强行因式分解就完事了。

$$\begin{aligned} &\left(n-\dfrac{-1+\sqrt{8a+1}}{2}\right)\left(n-\dfrac{-1-\sqrt{8a+1}}{2}\right)&\le&\ 0\\ \end{aligned} $$

其实这时你已经可以搞那个什么所谓的「穿针」大法，画个数轴，直接搞出 $n$ 的取值范围了。

不过这里其实没必要用那个方法其实是我懒得在电脑上画数轴再上传过来了。

因为

$$\begin{aligned} &\left(n-\dfrac{-1+\sqrt{8a+1}}{2}\right)\left(n-\dfrac{-1-\sqrt{8a+1}}{2}\right)&\le&\ 0\\ \end{aligned} $$

所以 $\left(n-\dfrac{-1+\sqrt{8a+1}}{2}\right)$ 与 $\left(n-\dfrac{-1-\sqrt{8a+1}}{2}\right)$ 一定是一正一负。

而显然有

$$\left(n-\dfrac{-1+\sqrt{8a+1}}{2}\right)<\left(n-\dfrac{-1-\sqrt{8a+1}}{2}\right) $$

所以必为

$$n-\dfrac{-1+\sqrt{8a+1}}{2}\le0,\quad n-\dfrac{-1-\sqrt{8a+1}}{2}\ge0 $$

所以我们得到了 $n$ 的取值范围：

$$\dfrac{-1-\sqrt{8a+1}}{2}\le n\le\dfrac{-1+\sqrt{8a+1}}{2} $$

所以 $n$ 的最大值就是 $\left\lfloor\dfrac{-1+\sqrt{8a+1}}{2}\right\rfloor$。

（由于显然 $n$ 是整数，再结合这个不等式的意义可知，需要加下取整）

$b$ 那边，也是同理的。结合这两边的结果，可以发现 $n$ 的最大值就是：

$$\min\left(\left\lfloor\dfrac{-1+\sqrt{8a+1}}{2}\right\rfloor,\left\lfloor\dfrac{-1+\sqrt{8b+1}}{2}\right\rfloor\right) $$

---

再转过头来，看看带上 $c$ 的情况。

由上面的那个求出 $n$ 的最小值的式子，我们不难看出，需要让 $a,b$ 中的最小值尽可能大！

那么，我们分类讨论：

不妨设 $a>b$。

（有没有同学忘记了 $a,b$ 的意义？

pigstd 有 $a$ 个 A 材料和 $b$ 个 B 材料

这就是 $a,b$ 的意义啦qwq。）

• 如果 $a+c\le b$，那么这 $c$ 块钱肯定都要花在材料 A 上，才能让他们中的最小值最大。
• 否则一定有 $a+c>b$，那么先花 $b-a$ 块钱，让材料 A 的个数等 于材料 B 的个数，然后 $a,b$ 各加上 $\left\lfloor\dfrac{c-b+a}{2}\right\rfloor$。

然后再直接套用上面的公式即可。复杂度 $O(1)$。

---

上代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>

#define LL long long

using namespace std;

LL a,b,c;

int main(void){

    scanf("%lld%lld%lld",&a,&b,&c);
    LL x=max(a,b),y=min(a,b);
    LL m=x-y;
    if(m>c){//如果 x-y>c,即 c+y>x，那就是分类讨论时的第一种情况。
        LL ans=(LL)(((LL)(floor(sqrt(8*(y+c)+1)))-1)/2);//套公式
        printf("%lld\n",ans);
        return 0;
    }
    else{//否则那就是第二种情况
        c-=m;
        LL ans=(LL)(((LL)(floor(sqrt(8*(x+(LL)(c/2))+1)))-1)/2);//套公式
        printf("%lld\n",ans);
    }

    return 0;
}