【模擬貪心】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);}

# 擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功