M30218: 狭路相逢

stack, http://cs101.openjudge.cn/practice/M30218/

#include <iostream>
#include <vector>

auto main() -> int {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int N;
  std::cin >> N;
  std::vector<int> st;

  while (N--) {
    int v;
    std::cin >> v;

    bool flag = true;
    while (flag && v < 0 && !st.empty() && st.back() > 0) {
      if (st.back() < -v)
        v = st.back() + v, st.pop_back();
      else if (st.back() == -v)
        st.pop_back(), flag = false;
      else
        st.back() += v, flag = false;
    }

    if (flag)
      st.push_back(v);
  }

  std::cout << st.size() << '\n';

  for (const auto &a : st)
    std::cout << a << ' ';
  return 0;
}

共用时30min

思路：简单的模拟, 维护两个栈即可. 被输出格式卡了一会, 一开始忘记输出存活总数了

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    deque<int> soldiers;
    vector<int> monsters;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) {
            int monster = -a[i];
            while (!soldiers.empty()) {
                int top = soldiers.back();
                soldiers.pop_back();
                if (top > monster) {
                    soldiers.push_back(top - monster);
                    break;
                } else if (top == monster) {
                    monster = 0;
                    break;
                } else {
                    monster -= top;
                }
            }

            if (soldiers.empty() && monster > 0) {
                monsters.push_back(-monster);
            }
        } else {
            soldiers.push_back(a[i]);
        }
    }

    cout << monsters.size() + soldiers.size() << endl;
    for (int monster : monsters) {
        cout << monster << " ";
    }
    for (int soldier : soldiers) {
        cout << soldier << " ";
    }
    return 0;
}