题解思路

该问题要求模拟一系列“玩家1对1对战”的过程，每轮选择当前生命值最小且不为0的两名玩家进行PK，直到无法匹配出两名玩家或所有玩家生命值归零。
显然，每轮都要快速地找到当前生命值最小的两名玩家，因此可以使用 优先队列(最小堆) 来维护玩家集合。

算法步骤

1. 初始化
   • 将编号和生命值均大于0的玩家以 (life, id) 为键插入最小堆。
2. 循环PK
   • 当堆中元素少于2时，终止循环。
   • 弹出堆顶的两名玩家 (life1, id1) 和 (life2, id2)。
   • 若 life1 == life2，则两人同归于尽，直接丢弃。
   • 否则，胜者为生命值较大的那位（设 life_big, id_big），剩余生命值 rem = life_big - life_smaint，计算新生命值 newLife = rem * 3，并将 (newLife, id_big) 重新插入堆中。
3. 输出结果
   • 循环结束后，若堆为空，则输出 -1；
   • 否则堆中仅剩一位玩家，弹出并输出其编号和生命值。

相关算法

• 优先队列（Priority Queue）
  用于动态维护一个集合，支持在 $O(\log N)$ 时间内的插入与删除最小元素操作。

复杂度分析

• 初始化建堆需要 $O(N)$（或 $O(N\log N)$ 若逐个插入）；
• 每轮PK涉及两次堆弹出和一次可能的堆插入，共 $O(\log N)$；
• 最多进行 $N-1$ 次PK，故总时间复杂度为 $O(N\log N)$
• 空间复杂度主要用于存储堆，最多 $O(N)$。

代码实现

Python

import sys
import heapq

MAX_LIFE = 2**31 - 1

def solve():
    input = sys.stdin.readline
    n = int(input().strip())
    lives = list(map(int, input().split()))
    
    # 最小堆，元素为 (life, id)
    heap = []
    for i, v in enumerate(lives, start=1):
        if v > 0:
            heapq.heappush(heap, (v, i))
    
    while len(heap) >= 2:
        life1, id1 = heapq.heappop(heap)
        life2, id2 = heapq.heappop(heap)
        if life1 == life2:
            # 同归于尽
            continue
        # 分出胜负
        if life1 > life2:
            life_big, id_big, life_smaint = life1, id1, life2
        else:
            life_big, id_big, life_smaint = life2, id2, life1
        rem = life_big - life_smaint
        new_life = rem * 3
        if new_life > MAX_LIFE:
            new_life = MAX_LIFE
        if new_life > 0:
            heapq.heappush(heap, (new_life, id_big))
    
    # 输出
    if not heap:
        print(-1)
    else:
        life, pid = heap[0]
        print(pid, life)

if __name__ == "__main__":
    solve()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static final int MAX_LIFE = Integer.MAX_VALUE;

    static class Player implements Comparable<Player> {
        int life, id;
        Player(int l, int i) { life = l; id = i; }
        @Override
        public int compareTo(Player o) {
            // 先按生命值升序，再按 id 升序
            if (life != o.life) return Integer.compare(life, o.life);
            return Integer.compare(id, o.id);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        PriorityQueue<Player> pq = new PriorityQueue<>();

        // 1. 初始化：只将生命值>0的玩家入堆
        for (int i = 1; i <= n; i++) {
            int v = Integer.parseInt(st.nextToken());
            if (v > 0) {
                pq.offer(new Player(v, i));
            }
        }

        // 2. 循环 PK
        while (pq.size() >= 2) {
            Player p1 = pq.poll();
            Player p2 = pq.poll();
            if (p1.life == p2.life) {
                // 同归于尽，直接丢弃
                continue;
            }
            // 胜者和败者
            Player win = p1.life > p2.life ? p1 : p2;
            Player lose = p1.life > p2.life ? p2 : p1;
            long rem = (long)win.life - lose.life;      // 防溢出用 long
            long nl = rem * 3;
            if (nl > MAX_LIFE) nl = MAX_LIFE;           // clamp
            if (nl > 0) {
                pq.offer(new Player((int)nl, win.id));
            }
        }

        // 3. 输出
        if (pq.isEmpty()) {
            System.out.println(-1);
        } else {
            Player ans = pq.peek();
            System.out.println(ans.id + " " + ans.life);
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

static const int MAX_LIFE = INT_MAX;

struct Player {
    int life;
    int id;
};

struct Cmp {
    bool operator()(const Player &a, const Player &b) const {
        // 小顶堆：生命值小的排在前，若相等按 id
        if (a.life != b.life) return a.life > b.life;
        return a.id > b.id;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    priority_queue<Player, vector<Player>, Cmp> pq;

    // 1. 初始化
    for (int i = 1; i <= n; ++i) {
        int v;
        cin >> v;
        if (v > 0) {
            pq.push({v, i});
        }
    }

    // 2. 循环 PK
    while (pq.size() >= 2) {
        Player p1 = pq.top(); pq.pop();
        Player p2 = pq.top(); pq.pop();
        if (p1.life == p2.life) {
            // 同归于尽
            continue;
        }
        // 胜负判定
        Player win = (p1.life > p2.life ? p1 : p2);
        Player lose = (p1.life > p2.life ? p2 : p1);
        long rem = (long)win.life - lose.life;
        long nl = rem * 3;
        if (nl > MAX_LIFE) nl = MAX_LIFE;   // clamp
        if (nl > 0) {
            pq.push({(int)nl, win.id});
        }
    }

    // 3. 输出
    if (pq.empty()) {
        cout << -1 << "\n";
    } else {
        Player ans = pq.top();
        cout << ans.id << " " << ans.life << "\n";
    }

    return 0;
}

题目内容

有一款游戏，里面有$N$个游戏玩家 $(1<=N<100000)$，每个玩家都有一个初始的生命能量值$lifePower(0<=lifePower<=2^{31-1})$

游戏规则：经过多玩家$1$对$1$ $PK$ 直到游戏结束，每一轮$PK$都是从游戏中尚存的所有玩家中挑选生命能量值最小且不为$0$的$2$个玩家进行$PK$(如果在挑选符合$PK$条件的$2$个玩家过程中，能量值相同的候选玩家有多个时，则挑选玩家编号小的玩家参与$PK$)，如是两个玩家的生命能量值相同，则$2$个玩家同归于尽，生命能量值都归为$0$，$PK$后都退出游戏；如果$2$个玩家的生命能量值不同，则能量值大的玩家胜出，$PK$过程胜出玩家会消耗掉另一个玩家的同等数量的生命能量值，但是$PK$胜出后，则剩余生命能量值会膨胀$3$倍(最大不超过$32$位有符号整数的最大值即 $2^{31}-1$)，即为该玩家最终的生命能量值为剩余生分能量值的$3$倍。$PK$胜出的玩家仍可继续游戏；

如果游戏无法挑选出$2$个符合条件的玩家进行$PK$时，游戏结束；

请设计一个高效的算法，让游戏按规则进行玩家PK，直到游戏结束。

输入描述

第一行为游戏玩家的数量，取值范围：$1<=N<100000$

第二行为空格间隔的 $N$ 个游戏玩家的生命能量值 $lifePower$，按照玩家编号从$1$到$N$排列。取值范围：$0<= lifePower <2^{31}-1$

输出描述

打印最后$PK$胜出玩家的编号和该玩家的最终生命能量值，以$1$个空格为间隔。如果游戏经过PK后，没有留存下来生命能量值大于$0$的玩家，则打印$-1$。

样例1

输入

4
2 5 1 8

输出

4 6

说明

第$1$轮$PK$，最小的$2$个玩家是玩家$1$和玩家$3$，生命能力值分别是$2$和$1$，玩家$1$胜出，剩余能量值为$1$，膨胀$3$倍后最终生命能量值为$3$

第$1$轮$PK$后所有玩家的生命能量值为:$3$ $5$ $0$ $8$

第$2$轮$PK$，最小的$2$个玩家是玩家$1$和玩家$2$，生命能力值分别是$3$和$5$，玩家$2$胜出，剩余能量值为$2$，膨胀$3$倍后最终生命能量值为$6$

第$2$轮$PK$后所有玩家的生命能量值为:$0$ $6$ $0$ $8$

第$3$轮$PK$，最小的$2$个玩家是玩家$2$和玩家$4$(也是最后$2$个玩家)，生命能量值分别是$6$和$8$，玩家$4$胜出，剩余能量值为$2$，膨胀$3$倍后最终生命能量值为$6$

第$3$轮$PK$后所有玩家的生命能量值为:$0$ $0$ $0$ $6$

返回 $4$ $6$

样例2

输入

3
2 5 9

输出

-1

说明

第$1$轮$PK$，最小的$2$个玩家是玩家$1$和玩家$2$，生命能力值分别是$2$和$5$，玩家$2$胜出，剩余能量值为$3$，膨胀$3$倍后最终生命能量值为$9$

第$1$轮$PK$后所有玩家的生命能量值为:$0$ $9$ $9$

第$2$轮$PK$，最小的$2$个玩家是玩家$2$和玩家$3$，生命能力值分别是$9$和$9$，同归于尽，最后游戏没有剩余玩家，返回$-1$