比武

题目

by 郑瑜

描述

有 \(N\) 个比武者排成一排. 事先已经得知他们的战力; 对于两个比武者, 若他们之间 (不包括他们自己) 没有人战力大于他们当中的较小战力, 则他们需要一次比武. 求比武次数.

提示: 对于任意比武者, 排在其前面且战力较小的人不会和排在其后面的人比武. \(1 \leq\) 战力 \(< 231\). 人数: 1-2: \(N \leq 1 \times 10^3\); 3-4测试样例: \(1 \times 10^3 < N \leq 1 \times 10^4\); 5-10测试样例: \(1 \times 10^4 < N \leq 5 \times 10^5\).

IO格式

输入:

N
第1个比武者战力
...

输出:

比武次数

样例

输入1:

8
2
7
1
6
5
3
4
2

输出1:

9

输入2:

5
4
2
2
2
5

输出2:

10

解答

思路

这道题是在约三个月前做的, 所以已经不太记得细节了.

具体而言, 我们以一种特殊栈 (单调栈) 来处理: 这种特殊栈以一个常数区间为单元存储, 并且维护 secLen (倒数第二个单元的区间长度).

计算方法是, 同一区间内总可以比武; 如果前一区间大于现区间, 可以将前一区间的最后一个人加入比武; 如果前一区间小于现区间, 那么, 我们将连续弹出前区间直至我们的栈重新单调. 计数的总原则是 cur 前面的不大于 cur 及大于 cur 的最后一个应当计入.

参考:

代码

#include <cstdio>
#include <stack>
using namespace std;

#define prf printf
#define scf scanf
#define ull size_t

template <typename T>
struct StkUnit {
    StkUnit(T _val) : val(_val), len(1){};
    T val;
    int len;
};

template <typename T>
struct Stk {
    Stk() : slen(0), secLen(0){};
    stack<StkUnit<T>> s;
    int slen;
    int secLen;
    void push(T);
    void pop();
    void popUnit();
    T& top();
    StkUnit<T>& topUnit();
};

template <typename T>
void Stk<T>::push(T _val) {
    if (slen == 0) {
        s.push(StkUnit<T>(_val));
        slen++;
    } else {
        if (_val == s.top().val)
            s.top().len++;
        else {
            secLen = s.top().len;
            s.push(StkUnit<T>(_val));
            slen++;
        }
    }
}

template <typename T>
void Stk<T>::pop() {
    if (slen == 0) return;
    auto& top = s.top();
    top.len--;
    if (top.len == 0) {
        s.pop();
        slen--;
        if (slen == 0 || slen == 1)
            secLen = 0;
        else {
            auto temp = s.top();
            s.pop();
            secLen = s.top().len;
            s.push(temp);
        }
    }
}

template <typename T>
void Stk<T>::popUnit() {
    if (slen == 0) return;
    s.pop();
    slen--;
    if (slen == 0 || slen == 1)
        secLen = 0;
    else {
        auto temp = s.top();
        s.pop();
        secLen = s.top().len;
        s.push(temp);
    }
}

template <typename T>
T& Stk<T>::top() {
    return s.top().val;
}

template <typename T>
StkUnit<T>& Stk<T>::topUnit() {
    return s.top();
}

int main() {
    int N;
    Stk<int> stk;
    scf("%d", &N);
    int cur;
    ull ret = N - 1;
    for (auto i = 0; i < N; i++) {
        scf("%d", &cur);
        if (stk.slen == 0) {
            stk.push(cur);
            continue;
        }
        auto& top = stk.top();
        if (cur < top) {
            stk.push(cur);
        } else if (cur == top) {
            ret += stk.topUnit().len - 1 + bool(stk.secLen);
            stk.push(cur);
        } else {
            stk.pop();
            while (stk.slen && stk.top() < cur) {
                ret += stk.topUnit().len;
                stk.popUnit();
            }
            if (stk.slen) {
                if (stk.top() > cur)
                    ret += bool(stk.topUnit().len);
                else if (stk.top() == cur)
                    ret += stk.topUnit().len + bool(stk.secLen);
            }
            stk.push(cur);
        }
    }
    prf("%llu", ret);
    return 0;
}

时空消耗

1	Accepted	0 ms	916 KB
2	Accepted	0 ms	920 KB
3	Accepted	0 ms	920 KB
4	Accepted	0 ms	916 KB
5	Accepted	36 ms	912 KB
6	Accepted	60 ms	912 KB
7	Accepted	68 ms	916 KB
8	Accepted	68 ms	2788 KB
9	Accepted	68 ms	2084 KB
10	Accepted	52 ms	916 KB