https://codeforces.com/contest/1902/problem/B
题目大意
有 $n \le 10^{9}$ 天，在第 $1, 8, 15, \cdots$ 天会放出任务，在当天或之后任何天都可以完成这个任务，每天都会有课程。每天可以选择休息，或上课并完成 $0 \sim 2$ 个还未完成的任务。上课获得 $pl \ (\le 10^9)$ 点，完成一个任务获得 $pt \ (\le 10^9)$ 点，问要得到至少 $p \ (\le 10^{18})$ 点，最多可以休息多少天。
简要题解
注意到，总是在最前面休息比较好，因为后面有更多可以做的任务。而在最后总是能做到做任务的上限（要么是所有任务的上限，要么是能做任务的上限）。除了最后一天刚好是 $7k + 1$ 时，其他的情况，我们总能保证做任务的日期 $i$ 严格大于任务放出的日期 $d$。（比如 $n$ 会做 $n$ 和 $n - 7$ 的任务，$n - 1$ 会做 $n - 14$ 和 $n - 21$）。那么随着不休息的日子增多，要么是上课做任务都增加，要么是上课增加（所有任务已经做完了），获得分数是单调的。于是二分加判断即可。
复杂度
$T$：$O(\log n)$
$S$：$O(1)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
LL n, p, pl, pt;
cin >> n >> p >> pl >> pt;
LL mx = (n + 6) / 7;
auto check = [&](LL mid) -> bool {
LL sum = mid * pl;
sum += min(mx, mid * 2) * pt;
// cout << mid << ' ' << sum << '\n';
return sum >= p;
};
LL l = 1, r = n;
LL mid, ans = r;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << (n - ans) << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Subtract Min Sort - Codeforces Round 998 (Div. 3)