【模拟贪心】B4207 [常州市赛 2021] 战士|普及+

B4207 [常州市赛 2021] 战士

题目背景

搬运自 http://czoj.com.cn/p/443。数据为民间数据。

题目描述

小 $\text X$ 在玩一款操控战士和怪物战斗的游戏。战士初始生命值为 $\text{iH}$ 、初始攻击力为 $\text{iA}$ 。怪物只有一个，初始生命值为 $H$ 。
战斗是回合制的，且有一个回合数限制 $M$ 。如果在 $M$ 回合内怪物还没有被杀死，小 $\text X$ 就失败了。在每个回合，战士先行动，怪物再行动。
每当战士行动，小 $\text X$ 可以命令战士做以下两件事中的一件：

攻击，让怪物的生命值减少当前战士攻击力的数值。
磨刀，让战士攻击力增加 $\text{dA}$ 。

每当怪物行动，怪物会攻击战士，使战士的生命值减少 $C_i$ ，其中 $i$ 为回合数。
当一个角色生命值小于等于 $0$ 时，角色会死亡。

如果怪物死亡，那么战斗就结束了。
如果战士死亡，会立刻复活，将生命值和攻击力恢复为初始数值。

现在小 $X$ 想问问你，最少能在几个回合内杀死怪物。

输入格式

第一行， $5$ 个整数，分别为 $\text{iH,iA},H,\text{dA},M$ ，意义见问题描述。
第二行 $M$ 个整数，表示第 $i$ 个回合怪物的攻击力 $C_i$ 。

输出格式

输出一行一个整数表示最少能在几个回合内杀死怪物。如果 $M$ 回合内杀不死，输出 -1。

输入输出样例 #1

输入 #1

4 1 6 1 8
2 1 1 1 1 1 1 1

输出 #1

说明/提示

样例解释

其中一种合法方案：

第一回合：战士磨刀，战士攻击力变为 $2$ ；怪物攻击，战士生命值变成 $2$ 。
第二回合：战士攻击，怪物生命值变为 $4$ ；怪物攻击，战士生命值变成 $1$ 。
第三回合：战士攻击，怪物生命值变为 $2$ ；怪物攻击，战士死亡后复活，生命值变为 $4$ ，攻击力变为 $1$ 。
第四回合：战士攻击，怪物生命值变为 $1$ ；怪物攻击，战士生命值变成 $3$ 。
第五回合：战士攻击，怪物死亡。

数据范围

本题共有 $10$ 个测试点。
对于所有数据， $1\le \text{iH,iA},H\le10^9,0\le \text{dA}\le10^9,1\le C_i\le M\le2\times10^5$ 。

测试点编号	$M$	特殊性质
$1$	$\le 2\times10^5$	$\text{dA}=0$
$2\sim3$	$\le20$	无
$4\sim5$	$\le30$	无
$6\sim8$	$\le10^3$	无
$9\sim10$	$\le2\times10^5$	无

模拟贪心

a[i]表示，不轮回的情况下，战士i回合操作的最大伤害。long long 型，如果大于LLONG_MAX/4，取LLONG_MAX/4。
dead=0，第dead回合轮回。hurt=0LL，记录轮回前的伤害。HP=iH记录战士剩余生命值。
枚举i = 1 to M
{ if(hurt + a[i-dead] >= H){return i ;}
if(C[i] >= HP){ HP=iH;dead=i;hurt += a[i-dead];}
else HP -= C[i]。}
return -1
计算a[i]
令磨刀x回合，显然先磨刀再攻击。总伤害,用a代替iA,d代替da：
$\Large(a+d \times x)(i-x)=a\times i + (i\times d -a)x - d \times x\times x 式子一$
$x^2-2x\frac{i\times d- a}{2d}$
float $\large f =\large \frac{i\times d -a }{d \times 2.0},式子一=-d(x-f)^2 + 某个常数$ 如果f是整数，x取f时最大值。
如果f不是整数，向下取整或向上取整时是最大值。枚举两种情况。
注意： $\lfloor \ f \rfloor,x2 = \lceil \ f \rceil$ 如果x1(x2) > i，取i。小于0,取0。
用3个样例，过不了。暴力枚举x，错误的样例能过，但超时。
说明：F函数正确，x的极值错误。
自己构造了N组数据，没发现错误。晚上睡觉前，灵光一现：a和d相差很大的时候是否有问题？
31号早上，一试果然如此？ $a == 3, d == 1$ 暴力算法和计算的x不一致。

a[i] = max(F(x1, i), F(x2, i));auto tmp = F(0, i);for (int j = 1; j < i; j++) {tmp = max(tmp, F(j, i));}//Assert::AreEqual(tmp, a[i]);assert(tmp== a[i]);;

i为1时，暴力计算的是3，解方程的是4。
最终发现错误原因：赋值号打成了等号。

if (x1 >= i) { x1 == i; }

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};
class Solution {public:int Ans(int iH, int iA, const int H, int dA, vector<int>& C){				const int M = C.size();vector<long long> a(M + 1);auto F = [&](long long x,long long i) {const long long ll1 = dA * x + iA;const long long ll2 = i - x;if (LLONG_MAX / ll1 < ll2) { return (long long) H; }return ll1 *ll2 ;};for (long long i = 1; i <= M; i++) {if (0 == dA) {a[i] = iA * i;continue;}const long long f1 = i * dA - iA;const long long f2 = dA * 2LL;long long x1 = f1 / f2;					long long x2 = x1 + (0 != f1 % f2);if (x1 >= i) { x1 = i; }if (x2 >= i) { x2 = i; }if (x1 < 0) { x1 = 0; }if (x2 < 0) { x2 = 0; }a[i] = max(F(x1, i), F(x2, i));					}int dead = 0;long long hurt = 0, HP = iH;	for (int m = 1; m <= M; m++) {if (hurt + a[m - dead] >= H) { return m; }if (C[m-1] >= HP) {HP = iH; hurt += a[m - dead]; dead = m;  }else { HP -= C[m-1]; }}return -1;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;	int iH,iA,H,dA,Q;cin>> iH >> iA >> H >> dA >> Q;auto C = Read<int>(Q);
#ifdef _DEBUG	printf("iH=%d,iA=%d,H=%d,dA=%d",iH,iA,H,dA);Out(C, ",C=");//Out(edge, ",edge=");		/*Out(que, ",que=");*///Out(ab, ",ab=");//Out(par, "par=");//Out(que, "que=");//Out(B, "B=");
#endif // DEBUG	auto res = Solution().Ans(iH, iA, H, dA, C);cout << res;return 0;
};

单元测试

	int iH, iA,  H,  dA;vector<int> C;TEST_METHOD(TestMethod01){iH = 4, iA = 1, H =1, dA = 0, C = { 2,1,1,1,1,1,1,1 };auto res = Solution().Ans(iH, iA, H, dA, C);AssertEx(1, res);}TEST_METHOD(TestMethod11){iH = 4, iA = 1, H = 6, dA = 1, C = { 2,1,1,1,1,1,1,1 };auto res = Solution().Ans(iH, iA, H, dA, C);AssertEx(5, res);}TEST_METHOD(TestMethod12){iH = 4, iA = 3, H = 4, dA =1 , C.assign(100'000,1);auto res = Solution().Ans(iH, iA, H, dA, C);AssertEx(2, res);}

# 扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功