14221: 【原4221】战士

题目

题目描述

author: Shuhao Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4221

Description

在X轴上有N个战士沿直线移动，每个战士有不同的初始位置，有的向左移动，有的向右移动，他们移动的速度是一样的。每一位战士都有一个武力值，当两战士相遇，武力值大的会瞬间将武力值小的干掉然后继续移动（干掉的过程不计时间）。

输入从左到右给出每位战士的武力值大小和移动的方向（0表示向左，1表示向右）。当经过足够长的时间之后，还剩下多少位战士？

Input Format

第一行一个整数N，表示战士的总数。

接下来总共N行，每行描述战士的武力值大小和移动方向。

第2到N+1行，每行两个整数a[i], b[i]。a[i]表示战士的武力值大小，b[i]表示移动方向，0表示向左，1表示向右。

Output Format

输出一个整数，表示经过足够长的时间以后，还剩下的战士的数目。

Sample Input

5
4 0
3 1
2 0
1 0
5 0

Sample Output

2

Limits

对于50%的数据，N <= 10000。

对于100%的数据，N <= 500000，0 <= a[i] < 10^8, b[i] = 0或1。

BugenZhao's solution

//
// Created by BugenZhao on 2019/4/10.
//

//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BSTACK_H
#define SBL_BSTACK_H


template<typename Item>
class BStack {
    class Node {
    public:
        Item item;
        Node *next;

        explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

        explicit Node(Node *next = nullptr) : next(next) {}

        virtual ~Node() = default;
    };

    int N;
    Node *top;

public:
    BStack() {
        top = nullptr;
        N = 0;
    }

    void push(const Item &item) {
        top = new Node{item, top};
        ++N;
    }

    Item peek() {
        return top->item;
    }

    Item pop() {
        Node *tmp = top;
        Item ret = top->item;
        top = top->next;
        delete tmp;
        --N;
        return ret;
    }

    int size() {
        return N;
    }

    void clear() {
        Node *tmp;
        while (top) {
            tmp = top;
            top = top->next;
            delete tmp;
        }
        top = nullptr;
        N = 0;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    virtual ~BStack() {
        Node *tmp;
        while (top) {
            tmp = top;
            top = top->next;
            delete tmp;
        }
    }

private:
    class Iterator {
        Node *it;
        Node *top;
    public:

        Iterator(Node *top) : it(top), top(top) {}

        bool hasNext() const {
            return it != nullptr;
        }

        Item &next() {
            Node *p = it;
            it = it->next;
            return p->item;
        }

        const Item &next() const {
            Node *p = it;
            it = it->next;
            return p->item;
        }
    };

public:
    Iterator iterator() const {
        return Iterator(top);
    }
};


#endif //SBL_BSTACK_H


class S {
public:
    int power;
    bool dir;
};


#include <iostream>

using namespace std;

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

    int N;
    cin >> N;

    BStack<S> stack;

    int power;
    bool dir;
    for (int i = 0; i < N; ++i) {
        cin >> power >> dir;

        while (!stack.isEmpty()) {
            if (stack.peek().dir == 0 || stack.peek().dir == dir) {
                stack.push(S{power, dir});
                break;
            } else {
                if (stack.peek().power >= power) {
                    break;
                } else {
                    stack.pop();
                }

            }
        }
        if (stack.isEmpty()) {
            stack.push(S{power, dir});
        }
    }
    cout << stack.size() << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "stack"
#include "cstdio"
using namespace std;

stack<int> stack_data;

int main() {
    int n;
    scanf("%d", &n);


    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int val, direction;
        scanf("%d %d", &val, &direction);
        if (direction) {
            stack_data.push(val);
        }
        else {
            while (!stack_data.empty()) {
                if (val >= stack_data.top())
                    stack_data.pop();
                else {
                    --ans;
                    break;
                }
            }
            ++ans;
        }
    }
    printf("%d", (int)stack_data.size() + ans);

    return 0;
}

skyzh's solution

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

int val[500003] = { 0 };
int dir[500003] = { 0 };

template <typename T>
class Stack {
public:
    T *data;
    int top_ptr;
    Stack(int cap) : data(new T[cap]), top_ptr(0) {}
    ~Stack() { delete[] data; }
    void push(const T& d) { data[top_ptr++] = d; }
    T pop() { return data[--top_ptr]; }
    T top() { return data[top_ptr - 1]; }
    bool empty() { return top_ptr == 0; }
};

int main() {
    int n;
    scanf("%d", &n);
    int l_ans = 0;
    for (int i = 0; i < n; i++) scanf("%d%d", &val[i], &dir[i]);
    Stack <int> x(500003);
    for (int i = n - 1; i >= 0; i--) {
        if (dir[i] == 0) {
            x.push(val[i]);
        } else {
            while (!x.empty() && val[i] > x.top()) {
                x.pop();
            }
            if (x.empty()) ++l_ans;
        }
    }
    printf("%d\n", l_ans + x.top_ptr);
    return 0;
}