J、旅店的小小死神

赛中没调出来~

Problem：

题意大概：白天和晚上分别有两次操作，白天：召唤+炼金or炼金+炼金，晚上：收集+炼金or炼金+炼金。（具体内容看题，不做赘述），求n天内收集到的灵魂最多数量

Ideas：

时间复杂度：o(logn)

我的做法是二分找答案，但是可以直接暴力，这里放上我的思路

分两种情况讨论：

• c * 4 <= a * x + 2 * c
• c * 4 > a * x + 2 * c

然后分别进行操作，第一种情况直接让白天都召唤+炼金，晚上收集+炼金即可

第二种情况需要前期白天召唤+炼金，晚上收集+炼金，后期只管炼金+炼金

主要是第二种做法：

通过二分去找答案，找到能够满足收集到的灵魂够后面使用的临界，然后再分别讨论该临界和比他小一的情况（完全利用残魂）

这里放代码

Code：

#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> PII;


void solve() {
    int x, a, b, c, n;
    cin >> x >> a >> b >> c >> n;
    int res = 0;

    if(c * 4 <= a * x + 2 * c) { // 够数但没必要
        res += (a * x + 2 * c) * n; // 每天都要用客户
        res -= c; // 第一天白天没残魂
        /* 该代码是暴力跑，按照题目意思 ,得使用__int128*/
//        __int128 sum = 0;
//         res = 0;
//         for(int i = 0; i < n; i++) {
//             if(sum >= c) res += c, sum -= c;
//             sum += a * x * b;
//             res += a * x;
//             if(sum >= c) res += c, sum -= c;
//         }
    }
    else { // 够数且有必要
        int res1 = 0;
        int l = 1, r = n; // 二分找答案（什么时候能够收集到后面都足够的灵魂）
        while(l < r) {
            int mid = l + r >> 1;
            if((a * x * b - 2 * c) * mid + c >= 4 * c * (n - mid)) r = mid;
            else l = mid + 1;
        }
        /* 前期正常用客户，后期只用残魂 */
        res += 4 * (n - l) * c;
        res += 2 * c * l - c + a * x * l;
        /* 考虑到有可能少收集一天但是能够让残魂利用率最大化 */
        l--;
        res = max(res, l * a * x + (2 * l - 1) * c + min((n - l) * 4 * c, a * b * x * l - (2 * l - 1) * c));
    }
    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}