Educational Codeforces Round 159 (Rated for Div. 2)
基本情况
A题秒了。
B题想出来贪心思想，也想出来怎么找最优解了，但实现极其复杂繁琐，最后以先超时优化后又错误的结果告终。
B. Getting Points
明显越后面开始学收益越高。
然后写了个简单粗暴的纯模拟，T了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using ll = long long;
int T;
ll n, l, t, p;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> T;
while (T--)
{
ll sum = 0, cnt = 0;
std::cin >> n >> p >> l >> t;
ll tn = n;
ll task = n / 7;
if (n % 7 != 0)
task = task + 1;
while (n)
{
bool ok = false;
int dy = (n % 7) ? (n % 7) : 7;
int wk = n / 7;
n -= dy;
if (dy)
wk = wk + 1;
if (wk < 2)
{
for (int i = 1; i <= dy; i++)
{
if (task == 0)
{
sum += (dy - i + 1) * l;
cnt += dy - i + 1;
if (sum >= p)
{
while (sum - l >= p)
{
cnt--;
sum -= l;
}
ok = true;
}
break;
}
sum += t + l;
cnt++;
if (sum >= p)
{
ok = true;
break;
}
task--;
}
continue;
}
for (int i = 1; i <= dy; i++)
{
if (task >= 2)
{
sum += 2 * t + l;
cnt++;
if (sum >= p)
{
ok = true;
break;
}
task -= 2;
}
else if (task >= 1)
{
sum += t + l;
cnt++;
if (sum >= p)
{
ok = true;
break;
}
task -= 1;
}
else
{
sum += l * (dy - i + 1);
cnt += dy - i + 1;
if (sum >= p)
{
while (sum - l >= p)
{
cnt--;
sum -= l;
}
ok = true;
}
break;
}
}
if (ok)
{
break;
}
}
std::cout << tn - cnt << std::endl;
}
return 0;
}
然后就想着去掉循环的部分，全部用式子直接算，但是太多要处理的细节了，码力拉了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using ll = long long;
int T;
ll n, l, t, p;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> T;
while (T--)
{
std::cin >> n >> p >> l >> t;
ll sum = 0, ans = 0;
ll tDay = n;
ll task = (n % 7 == 0) ? n / 7 : n / 7 + 1;
int dy, wk;
while (tDay != 0)
{
bool ok = false;
if (tDay % 7 == 0)
{
dy = 7, wk = tDay / 7 + 1;
}
else
{
dy = tDay % 7, wk = tDay / 7;
}
tDay -= dy;
if (wk == 1)
{
sum += t + dy * l;
ans += dy;
if (sum > p)
{
ans -= (sum - t - p) / l;
sum -= sum - t - p;
if (sum > p)
{
ans -= 1;
}
}
continue;
}
if (task <= dy * 2)
{
int task_day = task / 2;
if (task % 2 != 0)
task_day++;
int ntd = dy - task_day;
sum += task * t + dy * l;
ans += dy;
if (sum >= p)
{
ok = true;
if (sum > p)
{
if (sum - ntd * l <= p)
{
ans -= (sum - p) / l;
}
else
{
ans -= ntd;
if (task % 2 == 0)
ans -= (sum - p) / (l + t * 2);
else
{
sum -= (t + l);
ans -= 1;
if (sum > p)
{
ans -= (sum - p) / (l + t * 2);
}
}
}
}
break;
}
break;
}
else
{
task -= dy * 2;
sum += dy * (l + t * 2);
//printf("ans = %d, dy = %d\n", ans, dy);
ans += dy;
if (sum >= p)
{
ok = true;
if (sum > p)
{
ans -= (sum - p) / (l + t * 2);
}
break;
}
}
if (ok)
break;
}
std::cout << n - ans << std::endl;
}
return 0;
}
看了某佬的讲解，这题用二分答案简直轻松。
说白了，找最多休息天数，也就是找最少工作天数。
刚好符合二分答案最小的最大原则。（我居然没想到！）
直接二分最小天数 \(x\)，校验即可。
校验函数也很有说法：
bool check(ll x)
{
ll s = x * a + min(2 * x, (n + 6) / 7) * b;
return s >= p;
}
思路是直接课程的学分 \(x\times a\) 再加上作业的学分 \(\min((n+6)/7,2\times x)\times b\) 即可（如果作业数够就是 \(2\times x\)，不然就是 \((n + 6)/7\)，即总周数，即刷出的总作业数。
我一开始觉得不严谨，万一周数为 1 要怎么特判呢，还有就是怎么保证这些作业都能做完呢。
后面仔细想想，每周才刷一个作业出来，作业量是远远小于天数的，是肯定可以保证写完的。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
ll n, p, a, b;
bool check(ll x)
{
ll temp = x * a + min(x * 2, (n + 6) / 7) * b;
return temp >= p;
}
void solve()
{
cin >> n >> p >> a >> b;
ll l = 1, r = n, mid;
while (l <= r)
{
mid = l + r >> 1;
if (check(mid))
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
cout << n - l << endl;
}
int main()
{
ios::sync_with_stdio(false);
int _;
cin >> _;
while (_--)
solve();
}