AtCoder题解｜ABC 118C - Monsters Battle Royale

题目信息 📚

【题目描述】

There are $N$ monsters, numbered $1, 2, …, N$.

Initially, the health of Monster $i$ is $A_i$.

Below, a monster with at least $1$ health is called alive.

Until there is only one alive monster, the following is repeated:

A random alive monster attacks another random alive monster.
As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.

Find the minimum possible final health of the last monster alive.

【输入】

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\ldots$ $A_n$

【输出】

Print the minimum possible final health of the last monster alive.

【数据范围】

All values in the input are integers.

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$

【输入样例1】

4
2 10 8 40

【输出样例1】

When only the first monster keeps on attacking, the final health of the last monster will be $2$, which is minimum.

【输入样例2】

4
5 13 8 1000000000

【输出样例2】

【输入样例3】

3
1000000000 1000000000 1000000000

【输出样例3】

1000000000

【题目来源】

https://atcoder.jp/contests/abc118/tasks/abc118_c

题目解析 🍉

【题目分析】

法一：利用 set 的自动升序、$O(logn)$ 插入和 stack 模拟该过程。

法二：对于两个怪兽来说，互相攻击存活的最小血量，其实是他们的 $gcd$（更相减损法）

【C++代码】

set + stack 模拟 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n, tmp;

int main() {
    set<int> s;
    set<int>::iterator it;
    // 读入数据，并且将数据存入set中（自动升序）
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        s.insert(tmp);
    }

    // 用stack存储当前最小值
    stack<int> st;
    while (!s.empty()) {
        // 取出set中最小的元素，并且在set中"弹出"（利用set.erase）
        it = s.begin();
        s.erase(*it);

        // 若当前栈为空，将该元素直接存入栈中
        if (st.empty()) {
            st.push(*it);
        } else {
            // 当前栈非空，则将栈顶元素与该元素的取模值进行比较
            // 若取模值为0，说明该元素可以被栈顶元素一直攻击，直至消去
            int m = *it % st.top();
            if (m) {
                // 若取模值不为0，说明该元素可以被攻击到小于栈顶元素，且无法消去
                // 此时弹出栈顶元素，并将栈顶元素重新加入set
                // 往栈中推入更小的取模值
                s.insert(st.top());
                st.pop();
                st.push(m);
            }
        }
    }
    // 最后的栈顶元素即为答案
    cout << st.top() << endl;

    return 0;
}

更相减损法 - gcd ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N];

int main() {
    // 读入数据
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    // 求所有数的最大公约数，即为答案
    int ans = a[1];
    for (int i = 2; i <= n; i++) {
        ans = __gcd(ans, a[i]);
    }
    cout << ans << endl;

    return 0;
}