消耗体力爬得更高

Question

名字叫 LKX 的小朋友想要爬山，他有一个体力条，当该体力条耗尽后，他就不能再往上爬了。

假设 LKX 的体力条数值为正整数 \(S\)，他有两种攀爬方式，一种是爬行，消耗 \(1\) 体力，向上爬 \(a\) 米；另一种是跳跃，消耗 \(b\) 体力，向上跳 \(c\) 米。

如果剩余的体力值小于 \(b\) 它仍然可以消耗掉剩余体力往上跳越 \(c\) 米；

问该小朋友 LKX 最大能爬多少米？

输入：

第一行输入一个整数 \(t\) 代表有 \(t\) 个测试；

对于剩下的 \(t\) 行，每行都是一个测试点，每个测试点都包含 \(4\) 个正整数：\(a, b, c, S\)。

输出：

输出 \(t\) 行，每行一个正整数，代表所能爬的最大高度。

数据保证：

\(t \in [1, 30000]\)

\(a, b, c, S \in [1, 10^9]\)

最初的想法就是先比较一下单位体力下的那种攀爬方式更高；

如果 \(a >= \frac{c}{b}\)，那么前 \(S - 1\) 份体力肯定是采取向上爬行的方式，那么剩下的一体力是可以选择跳跃或者继续向上爬行的，取决因素是 \(\max(a, c)\)，所以这种情况下的最优值为：

\((S - 1) \times a + \max(a, c)\)

如果 \(a < \frac{c}{b}\)，那么肯定有：\(c > a\) 这是显然的，我们索性立马抽出 \(1\) 体力代表最终要用 \(1\) 体力跳跃 \(c\) 米；

接着对于剩下的 \(S - 1\) 体力，要分割成 \(\left \lfloor \frac{S - 1}{b} \right \rfloor\) 份，对于每一份要跳跃 \(c\) 米，对于剩下的 \(S - 1 - \left \lfloor \frac{S - 1}{b} \right \rfloor\) 都要向上爬行 \(a\) 米；

所以可凝练出表达式：

\(c + \left \lfloor \frac{S - 1}{b} \right \rfloor * c + ((S - 1) \bmod b) * a\)

Code

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define endl '\n'
#define pique priority_queue
#define oier \
            ios_base::sync_with_stdio(false);\
            cin.tie(nullptr); cout.tie(nullptr);

#define cf int t; cin >> t; while (t --)

#define upfor(i, l, r) for (i = (l); i <= (r); i ++)
#define downfor(i, l, r) for (i = (r); i >= (l); i --)

// #define int long long
typedef long long LL;
typedef long double LD;
//typedef __int128_t int128;

const int inf = ~(1 << 31);  // 正无穷
const int ninf = (1 << 31);  // 负无穷

const LL infll = ~(1ll << 63); // 正无穷
const LL ninfll = (1ll << 63); // 负无穷

inline LL rll() { oier LL x; cin >> x; return x; }
inline int rint() { oier int x; cin >> x; return x; }

const int N = int (1e7 + 10);

// 由于情报不足，只能透过「试行错误」来获取。

/* =============================代码区============================= */

LL t, a, b, c, S;

void solve()
{   oier
    /* =========================== */

    cin >> t;
    while (t --)
    {
        cin >> a >> b >> c >> S;
        LL res = (a * b >= c) ? (S - 1) * a + max(a, c) : ((S - 1) / b + 1) * c + ((S - 1) % b) * a;
        cout << res << endl;
    }

    /* =========================== */
}

/* =============================代码区============================= */

/**
*                             _ooOoo_
*                            o8888888o
*                            88" . "88
*                            (| -_- |)
*                            O\  =  /O
*                         ____/`---'\____
*                       .'  \\|     |//  `.
*                      /  \\|||  :  |||//  \
*                     /  _||||| -:- |||||-  \
*                     |   | \\\  -  /// |   |
*                     | \_|  ''\---/''  |   |
*                     \  .-\__  `-`  ___/-. /
*                   ___`. .'  /--.--\  `. . __
*                ."" '<  `.___\_<|>_/___.'  >'"".
*               | | :  `- \`.;`\ _ /`;.`/ - ` : | |
*               \  \ `-.   \_ __\ /__ _/   .-` /  /
*          ======`-.____`-.___\_____/___.-`____.-'======
*                             `=---='
*          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
*                     佛祖保佑        永无BUG
*            佛曰:
*                   写字楼里写字间，写字间里程序员；
*                   程序人员写程序，又拿程序换酒钱。
*                   酒醒只在网上坐，酒醉还来网下眠；
*                   酒醉酒醒日复日，网上网下年复年。
*                   但愿老死电脑间，不愿鞠躬老板前；
*                   奔驰宝马贵者趣，公交自行程序员。
*                   别人笑我忒疯癫，我笑自己命太贱；
*                   不见满街漂亮妹，哪个归得程序员？
**/

/* ========================佛祖保佑, 永无bug======================== */

int main()
{
    // oier cf solve(); return 0;
    oier solve(); return 0;
}