cfgym103931C CCoffee Overdose

单峰

1.cfgym103931 CCoffee Overdose

题目描述

我们用体力 S 来表示你的精神状态。在每一秒钟，你为你的项目贡献 S 的完成度，之后你的体力会减 少 1。当你的体力减少到 0 或更少时，你会彻底失控并进入梦乡。 你可以在每秒钟刚好开始时喝下一杯咖啡，效果将会持续 C 秒。在咖啡的持续时间里，你不能再喝 另一杯咖啡，同时你的体力也将被固定在开始喝咖啡时的状态。在效果结束后，你的体力将立刻减少 C + 1，也即咖啡会让你额外感到 1 点体力的疲劳。 你的目标是在你睡着前爆发出生产力。对于给定的 S 和 C，你需要给出一个最优的安排，使总的完成度 最大化。

题目分析

假设在精力为u的时候喝咖啡，那么其在$t$到$t+c$的时间精力都保持u，$t+1+c$的时间后集体下降1，那么这个咖啡对整体的贡献值为$\frac{c(c-1)}{2}-(u-c)$所以当$u-v\ge \frac{c(c-1)}{2}$时喝咖啡可以产生贡献。贪心可得，假设其在$t$喝完咖啡之后肯定是接着一直喝咖啡。那么其可以被划分为若干段，且最后一次喝咖啡时的体力处于$x\in[0-c]$。这些值可以对应出来一个最大的$u$使得$u = k(c+1)+x$，而且这个u满足上面的柿子。然后可以发现k是关于x的一个分段函数，当其为x时对答案的贡献是$\frac{(x+k(c+1)+x)*(k+1)}{2}-\frac{(x+k(c+1)+1)*(x+k(c+1))}{2}$.然后通过判断鸡汁点进行$O(1)$计算或者进行三分。

代码

#include <vector>
#include <algorithm>
#include <iostream>
#include <array>

using ll = long long;

void sol() {
	ll s, c;
	std::cin >> s >> c;
	auto cacal = [&](ll x) {
		if (x > s)return 0ll;
		ll rem = x % (c + 1);
		ll len = x / (c + 1) + 1;
		return (x + rem) * len / 2 * c - x * (x + 1) / 2;
	};
	std::cout << 1ll * s * (s + 1) / 2 + std::max({cacal(s), cacal(c / 2 * c), cacal(s / c * c)}) << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int t;
	std::cin >> t;
	while (t--) {
		sol();
	}

	return 0;
}