小红的兽

[题目链接](https://www.nowcoder.com/practice/c0503d04a0324dac8bd85507773d8a80)

思路

本题是一道模拟题，按照题意逐轮处理遭遇事件即可。

战斗触发条件

两个单位 和 遭遇时， 表示 是否向 公布身份， 表示 是否向 公布身份。战斗是否发生取决于以下规则：

  1. 兽发现对方是人：如果 是兽，且 公布了身份（），且 是人，则兽主动攻击，战斗发生。反之亦然。
  2. 人发现对方是兽：如果 是人，且 公布了身份（），且 是兽，则人只在自己战斗力严格大于对方时才发起攻击。反之亦然。
  3. 同阵营：无论是否公布身份，都不会发生战斗。

注意：只要上述任一条件触发战斗，战斗就会发生（可能双方各自独立判断，任一方决定攻击即可）。

战斗结果

  • 战斗力高的一方获胜，另一方死亡。
  • 战斗力相等则同归于尽。

实现要点

  • 维护每个单位的存活状态，如果遭遇的某一方已经死亡，跳过该轮。
  • 按输入顺序逐轮模拟即可。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    vector<string> identity(n+1);
    vector<int> power(n+1);
    vector<bool> alive(n+1, true);
    for(int i = 1; i <= n; i++){
        char s[20];
        scanf("%s%d", s, &power[i]);
        identity[i] = s;
    }
    for(int i = 0; i < q; i++){
        int a, b;
        char ca, cb;
        scanf("%d%d %c %c", &a, &b, &ca, &cb);
        if(!alive[a] || !alive[b]) continue;
        bool fight = false;
        if(identity[a] == "monster" && cb == 'Y' && identity[b] == "human") fight = true;
        if(identity[b] == "monster" && ca == 'Y' && identity[a] == "human") fight = true;
        if(identity[a] == "human" && cb == 'Y' && identity[b] == "monster" && power[a] > power[b]) fight = true;
        if(identity[b] == "human" && ca == 'Y' && identity[a] == "monster" && power[b] > power[a]) fight = true;
        if(fight){
            if(power[a] == power[b]) alive[a] = alive[b] = false;
            else if(power[a] > power[b]) alive[b] = false;
            else alive[a] = false;
        }
    }
    for(int i = 1; i <= n; i++) printf("%c", alive[i] ? 'Y' : 'N');
    printf("\n");
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), q = sc.nextInt();
        String[] identity = new String[n + 1];
        int[] power = new int[n + 1];
        boolean[] alive = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            identity[i] = sc.next();
            power[i] = sc.nextInt();
            alive[i] = true;
        }
        for (int i = 0; i < q; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            char ca = sc.next().charAt(0), cb = sc.next().charAt(0);
            if (!alive[a] || !alive[b]) continue;
            boolean fight = false;
            if (identity[a].equals("monster") && cb == 'Y' && identity[b].equals("human")) fight = true;
            if (identity[b].equals("monster") && ca == 'Y' && identity[a].equals("human")) fight = true;
            if (identity[a].equals("human") && cb == 'Y' && identity[b].equals("monster") && power[a] > power[b]) fight = true;
            if (identity[b].equals("human") && ca == 'Y' && identity[a].equals("monster") && power[b] > power[a]) fight = true;
            if (fight) {
                if (power[a] == power[b]) { alive[a] = alive[b] = false; }
                else if (power[a] > power[b]) alive[b] = false;
                else alive[a] = false;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) sb.append(alive[i] ? 'Y' : 'N');
        System.out.println(sb.toString());
    }
}

import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    identity = [''] * (n + 1)
    power = [0] * (n + 1)
    alive = [True] * (n + 1)
    for i in range(1, n + 1):
        parts = input().split()
        identity[i] = parts[0]
        power[i] = int(parts[1])
    for _ in range(q):
        parts = input().split()
        a, b = int(parts[0]), int(parts[1])
        ca, cb = parts[2], parts[3]
        if not alive[a] or not alive[b]:
            continue
        fight = False
        if identity[a] == "monster" and cb == 'Y' and identity[b] == "human":
            fight = True
        if identity[b] == "monster" and ca == 'Y' and identity[a] == "human":
            fight = True
        if identity[a] == "human" and cb == 'Y' and identity[b] == "monster" and power[a] > power[b]:
            fight = True
        if identity[b] == "human" and ca == 'Y' and identity[a] == "monster" and power[b] > power[a]:
            fight = True
        if fight:
            if power[a] == power[b]:
                alive[a] = alive[b] = False
            elif power[a] > power[b]:
                alive[b] = False
            else:
                alive[a] = False
    print(''.join('Y' if alive[i] else 'N' for i in range(1, n + 1)))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const [n, q] = lines[idx++].split(' ').map(Number);
    const identity = new Array(n + 1);
    const power = new Array(n + 1);
    const alive = new Array(n + 1).fill(true);
    for (let i = 1; i <= n; i++) {
        const parts = lines[idx++].split(' ');
        identity[i] = parts[0];
        power[i] = parseInt(parts[1]);
    }
    for (let i = 0; i < q; i++) {
        const parts = lines[idx++].split(' ');
        const a = parseInt(parts[0]), b = parseInt(parts[1]);
        const ca = parts[2], cb = parts[3];
        if (!alive[a] || !alive[b]) continue;
        let fight = false;
        if (identity[a] === "monster" && cb === 'Y' && identity[b] === "human") fight = true;
        if (identity[b] === "monster" && ca === 'Y' && identity[a] === "human") fight = true;
        if (identity[a] === "human" && cb === 'Y' && identity[b] === "monster" && power[a] > power[b]) fight = true;
        if (identity[b] === "human" && ca === 'Y' && identity[a] === "monster" && power[b] > power[a]) fight = true;
        if (fight) {
            if (power[a] === power[b]) { alive[a] = alive[b] = false; }
            else if (power[a] > power[b]) alive[b] = false;
            else alive[a] = false;
        }
    }
    let res = '';
    for (let i = 1; i <= n; i++) res += alive[i] ? 'Y' : 'N';
    console.log(res);
});

复杂度分析

  • 时间复杂度：，读入 个单位信息，逐轮处理 次遭遇，每次 。
  • 空间复杂度：，存储每个单位的身份、战斗力和存活状态。