深圳网站建设hi0755,网站首页三张海报做多大,做网站最小的字体是多少钱,南通网站建设外包B4207 [常州市赛 2021] 战士
题目背景
搬运自 http://czoj.com.cn/p/443。数据为民间数据。
题目描述
小 X \text X X 在玩一款操控战士和怪物战斗的游戏。战士初始生命值为 iH \text{iH} iH 、初始攻击力为 iA \text{iA} iA 。怪物只有一个#xff0c;初始生命值为 H…B4207 [常州市赛 2021] 战士
题目背景
搬运自 http://czoj.com.cn/p/443。数据为民间数据。
题目描述
小 X \text X X 在玩一款操控战士和怪物战斗的游戏。战士初始生命值为 iH \text{iH} iH 、初始攻击力为 iA \text{iA} iA 。怪物只有一个初始生命值为 H H H 。 战斗是回合制的且有一个回合数限制 M M M 。如果在 M M M 回合内怪物还没有被杀死小 X \text X X 就失败了。在每个回合战士先行动怪物再行动。 每当战士行动小 X \text X X 可以命令战士做以下两件事中的一件
攻击让怪物的生命值减少当前战士攻击力的数值。磨刀让战士攻击力增加 dA \text{dA} dA 。
每当怪物行动怪物会攻击战士使战士的生命值减少 C i C_i Ci 其中 i i i 为回合数。 当一个角色生命值小于等于 0 0 0 时角色会死亡。
如果怪物死亡那么战斗就结束了。如果战士死亡会立刻复活将生命值和攻击力恢复为初始数值。
现在小 X X X 想问问你最少能在几个回合内杀死怪物。
输入格式
第一行 5 5 5 个整数分别为 iH,iA , H , dA , M \text{iH,iA},H,\text{dA},M iH,iA,H,dA,M意义见问题描述。 第二行 M M M 个整数表示第 i i i 个回合怪物的攻击力 C i C_i Ci 。
输出格式
输出一行一个整数表示最少能在几个回合内杀死怪物。如果 M M M 回合内杀不死输出 -1。
输入输出样例 #1
输入 #1
4 1 6 1 8
2 1 1 1 1 1 1 1输出 #1
5说明/提示
样例解释
其中一种合法方案
第一回合战士磨刀战士攻击力变为 2 2 2 怪物攻击战士生命值变成 2 2 2。第二回合战士攻击怪物生命值变为 4 4 4 怪物攻击战士生命值变成 1 1 1 。第三回合战士攻击怪物生命值变为 2 2 2 怪物攻击战士死亡后复活生命值变为 4 4 4 攻击力变为 1 1 1 。第四回合战士攻击怪物生命值变为 1 1 1 怪物攻击战士生命值变成 3 3 3 。第五回合战士攻击怪物死亡。
数据范围
本题共有 10 10 10 个测试点。 对于所有数据 1 ≤ iH,iA , H ≤ 10 9 , 0 ≤ dA ≤ 10 9 , 1 ≤ C i ≤ M ≤ 2 × 10 5 1\le \text{iH,iA},H\le10^9,0\le \text{dA}\le10^9,1\le C_i\le M\le2\times10^5 1≤iH,iA,H≤109,0≤dA≤109,1≤Ci≤M≤2×105。
测试点编号 M M M特殊性质 1 1 1 ≤ 2 × 10 5 \le 2\times10^5 ≤2×105 dA 0 \text{dA}0 dA0 2 ∼ 3 2\sim3 2∼3 ≤ 20 \le20 ≤20无 4 ∼ 5 4\sim5 4∼5 ≤ 30 \le30 ≤30无 6 ∼ 8 6\sim8 6∼8 ≤ 10 3 \le10^3 ≤103无 9 ∼ 10 9\sim10 9∼10 ≤ 2 × 10 5 \le2\times10^5 ≤2×105无
模拟 贪心
a[i]表示不轮回的情况下战士i回合操作的最大伤害。long long 型如果大于LLONG_MAX/4取LLONG_MAX/4。 dead0第dead回合轮回。hurt0LL记录轮回前的伤害。HPiH记录战士剩余生命值。 枚举i 1 to M { if(hurt a[i-dead] H){return i ;} if(C[i] HP){ HPiH;deadi;hurt a[i-dead];} else HP - C[i]。} return -1 计算a[i] 令磨刀x回合显然先磨刀再攻击。总伤害,用a代替iA,d代替da ( a d × x ) ( i − x ) a × i ( i × d − a ) x − d × x × x 式子一 \Large(ad \times x)(i-x)a\times i (i\times d -a)x - d \times x\times x 式子一 (ad×x)(i−x)a×i(i×d−a)x−d×x×x式子一 x 2 − 2 x i × d − a 2 d x^2-2x\frac{i\times d- a}{2d} x2−2x2di×d−a float f i × d − a d × 2.0 , 式子一 − d ( x − f ) 2 某个常数 \large f \large \frac{i\times d -a }{d \times 2.0},式子一-d(x-f)^2 某个常数 fd×2.0i×d−a,式子一−d(x−f)2某个常数 如果f是整数x取f时最大值。 如果f不是整数向下取整或向上取整时是最大值。枚举两种情况。 注意 x 1 ⌊ f ⌋ , x 2 ⌈ f ⌉ x1 \lfloor \ f \rfloor,x2 \lceil \ f \rceil x1⌊ f⌋,x2⌈ f⌉ 如果x1(x2) i取i。小于0,取0。 用3个样例过不了。暴力枚举x错误的样例能过但超时。 说明F函数正确x的极值错误。 自己构造了N组数据没发现错误。晚上睡觉前灵光一现a和d相差很大的时候是否有问题 31号早上一试果然如此 a 3 , d 1 a3,d1 a3,d1 暴力算法和计算的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
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist
#includearray#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T1, class T2, class T3, class T4, class T5, class T6, class T7
std::istream operator (std::istream in, tupleT1, T2, T3, T4,T5,T6,T7 t) {in get0(t) get1(t) get2(t) get3(t) get4(t) get5(t) get6(t);return in;
}templateclass T int
vectorT Read() {int n;cin n;vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}
templateclass T int
vectorT ReadNotNum() {vectorT ret;T tmp;while (cin tmp) {ret.emplace_back(tmp);if (\n cin.get()) { break; }}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 1000000
class CInBuff
{
public:inline CInBuff() {}inline CInBuffN operator(char ch) {FileToBuf();while ((\r *S) || (\n *S) || ( *S)) { S; }//忽略空格和回车ch *S;return *this;}inline CInBuffN 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;}templateclass T1, class T2inline CInBuff operator(pairT1, T2 val) {*this val.first val.second;return *this;}templateclass T1, class T2, class T3inline CInBuff operator(tupleT1, T2, T3 val) {*this get0(val) get1(val) get2(val);return *this;}templateclass T1, class T2, class T3, class T4inline CInBuff operator(tupleT1, T2, T3, T4 val) {*this get0(val) get1(val) get2(val) get3(val);return *this;}templateclass T intinline CInBuff operator(vectorT val) {int n;*this n;val.resize(n);for (int i 0; i n; i) {*this val[i];}return *this;}templateclass T intvectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {*this ret[i];}return ret;}templateclass T intvectorT Read() {vectorT 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, vectorint C){ const int M C.size();vectorlong 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; COutBuff10000000 ob; int iH,iA,H,dA,Q;cin iH iA H dA Q;auto C Readint(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;vectorint 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(100000,1);auto res Solution().Ans(iH, iA, H, dA, C);AssertEx(2, res);}# 扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
