题目链接：
题目分析
模拟！纯粹按照题目描述模拟！
这是一道喜闻乐见的经典模拟题！
我一共写了2遍，Debug 历时2天的所有晚自习 ... 时间超过 8h ... 我真是太弱了啊 ...
最终对着数据和 std 终于找到错误了！
错误：好好读题！不要忽略题意中的细节！在函数中提前退出的时候想想会不会有什么事情还没有做。
Warning!Warning!Warning!
注意在给 sort 写 Cmp 的时候，一定一定一定要保证比较结果双向统一！ 若 Cmp(a, b) == false , 那么 Cmp(b, a) 一定要为 true ！！！
否则就会跪掉！一定要注意！Cmp里有一些特殊条件判断的时候一定要注意这一点！
代码
#include#include #include #include #include #include using namespace std; typedef double DB; const int MaxN = 8 + 3, MaxA = 6 + 3, MaxB = 20 + 3, INF = 999999999;const int Dx[5] = {0, 1, 0, -1}, Dy[5] = {1, 0, -1, 0}; int n, m, B_s, B_d, B_r, Time, Ant_Index, Target, Ant_s, Over_Time, Lev_Now;int Msg[MaxN][MaxN], Tgt[MaxB]; DB Hp_Now; bool Map[MaxN][MaxN]; inline int gmin(int a, int b) {return a < b ? a : b;}inline int gmax(int a, int b) {return a > b ? a : b;} struct Battery{ int x, y;} B[MaxB]; inline bool OKP(int x, int y) { if (x < 0 || x > n) return false; if (y < 0 || y > m) return false; return (!Map[x][y]);} struct Ant{ int Hp, Hp_Ceiling, Lev, Age, x, y, Lx, Ly; bool Alive, Cake; Ant() { x = y = 0; Lx = Ly = -1; Age = 0; Lev = Lev_Now; Hp = Hp_Ceiling = (int)Hp_Now; Alive = true; Cake = false; } void Move() { int MaxMsg = -1, nk = -1, xx, yy; for (int i = 0; i < 4; ++i) { xx = x + Dx[i]; yy = y + Dy[i]; if (!OKP(xx, yy) || (xx == Lx && yy == Ly)) continue; if (Msg[xx][yy] > MaxMsg) { MaxMsg = Msg[xx][yy]; nk = i; } } if (MaxMsg == -1) { Lx = x; Ly = y; return; } if ((Age + 1) % 5 == 0) { while (true) { nk = ((nk - 1) + 4) % 4; xx = x + Dx[nk]; yy = y + Dy[nk]; if (!OKP(xx, yy) || (xx == Lx && yy == Ly)) continue; break; } } Lx = x; Ly = y; x += Dx[nk]; y += Dy[nk]; Map[Lx][Ly] = false; Map[x][y] = true; } void GetCake() { Cake = true; Hp = gmin(Hp_Ceiling, Hp + (Hp_Ceiling >> 1)); } void Print() { printf("%d %d %d %d %d\n", Age, Lev, Hp, x, y); }} A[MaxA]; void Init() { for (int i = 1; i <= 6; ++i) { A[i].Alive = false; A[i].Cake = false; } Hp_Now = 4.4; Lev_Now = 1; Ant_Index = 0; memset(Map, 0, sizeof(Map)); for (int i = 1; i <= B_s; ++i) Map[B[i].x][B[i].y] = true; memset(Msg, 0, sizeof(Msg)); Ant_s = 0; Target = -1; Over_Time = -1;} void New_Ant_Born() { if (Map[0][0] || Ant_s == 6) return; ++Ant_Index; if (Ant_Index == 7) { Ant_Index = 1; Hp_Now *= 1.1; ++Lev_Now; } A[++Ant_s] = Ant(); Map[0][0] = true;} void Add_Message() { for (int i = 1; i <= Ant_s; ++i) { if (Target == i) Msg[A[i].x][A[i].y] += 5; else Msg[A[i].x][A[i].y] += 2; }} void Ant_Move() { for (int i = 1; i <= Ant_s; ++i) { A[i].Move(); if (Target == -1 && A[i].x == n && A[i].y == m) { Target = i; A[i].GetCake(); } }} inline int Sqr(int x) {return x * x;}inline int Abs(int x) {return x < 0 ? -x : x;} int SqrDis(int x, int y, int xx, int yy) { return Sqr(x - xx) + Sqr(y - yy);} int Nearest(int x, int y) { int MinDis = INF, Dx, ret; for (int i = 1; i <= Ant_s; ++i) { Dx = SqrDis(A[i].x, A[i].y, x, y); if (Dx < MinDis) { ret = i; MinDis = Dx; } } return ret;} bool Intersect(int x, int y, int xa, int ya, int xb, int yb) { if (x < gmin(xa, xb) || x > gmax(xa, xb) || y < gmin(ya, yb) || y > gmax(ya, yb)) return false; int S2; S2 = Abs(xa * yb + y * xb + x * ya - y * xa - x * yb - xb * ya); S2 = Sqr(S2); return (S2 * 4 <= SqrDis(xa, ya, xb, yb));} void Battery_Attack() { if (Target == -1) for (int i = 1; i <= B_s; ++i) Tgt[i] = Nearest(B[i].x, B[i].y); else for (int i = 1; i <= B_s; ++i) if (SqrDis(B[i].x, B[i].y, A[Target].x, A[Target].y) <= Sqr(B_r)) Tgt[i] = Target; else Tgt[i] = Nearest(B[i].x, B[i].y); for (int i = 1; i <= B_s; ++i) { if (SqrDis(B[i].x, B[i].y, A[Tgt[i]].x, A[Tgt[i]].y) > Sqr(B_r)) continue; for (int j = 1; j <= Ant_s; ++j) if (Intersect(A[j].x, A[j].y, B[i].x, B[i].y, A[Tgt[i]].x, A[Tgt[i]].y)) A[j].Hp -= B_d; } int Temp = 0; for (int i = 1; i <= Ant_s; ++i) { if (A[i].Hp >= 0) continue; A[i].Alive = false; Map[A[i].x][A[i].y] = false; if (A[i].Cake) { Target = -1; A[i].Cake = false; } ++Temp; } Ant_s -= Temp;} bool Check_Over() { if (Target == -1) return false; return (A[Target].x == 0 && A[Target].y == 0);} void Decrease_Message() { for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) if (Msg[i][j] > 0) --Msg[i][j];} bool Cmp(Ant a1, Ant a2) { if (a1.Alive == false && a2.Alive) return false; if (a1.Alive && a2.Alive == false) return true; return a1.Age > a2.Age;} void Update_Ant() { sort(A + 1, A + 6 + 1, Cmp); for (int i = 1; i <= Ant_s; ++i) { ++A[i].Age; if (A[i].Cake) Target = i; }} void Print_Situation() { printf("%d\n", Ant_s); for (int i = 1; i <= Ant_s; ++i) A[i].Print();} int main() { scanf("%d%d", &n, &m); scanf("%d%d%d", &B_s, &B_d, &B_r); for (int i = 1; i <= B_s; ++i) scanf("%d%d", &B[i].x, &B[i].y); scanf("%d", &Time); Init(); for (int i = 1; i <= Time; ++i) { New_Ant_Born(); Add_Message(); Ant_Move(); Battery_Attack(); if (Check_Over()) { sort(A + 1, A + 6 + 1, Cmp); Over_Time = i; break; } Decrease_Message(); Update_Ant(); } if (Over_Time != -1) printf("Game over after %d seconds\n", Over_Time); else printf("The game is going on\n"); Print_Situation(); return 0;}