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();
}