AOJ:Areas on the Cross-Section Diagram水域面积

ALDS1_3_D < Lesson < Courses | Aizu Online Judge (u-aizu.ac.jp)题目来源

我们这里使用栈的思想来解题

当我们遇见‘\’时就将对应位置编号i存入栈a1中，遇到‘/’时，根据栈先入后出的原则，我们每次提出的‘\’都是除对应外最邻近的。直接计算面积可以用此时的i减去‘\’的编号。

面积的问题解决了，但是还需要计算每个水坑的面积以及有多少水坑。这里我们再做一个栈a2，用来存每次算完面积时‘\’的编号和对应小坑面积，如果下一个‘/’对应得‘\’在栈中最上方元素的前面，那么这两个就是一个水坑，我们让面积相加，并更新a2中的值。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int main(){
    string s;
    int sum=0;
    stack<int>a1;
    stack<pair<int ,int> >a2;
    cin>>s;
    s=" "+s;
    for (int i = 1; i <s.length() ; ++i) {
        if(s[i]=='\\'){
            a1.push(i);

        }else if(s[i]=='/'&&a1.size()>0){
            int x=a1.top();
            a1.pop();
            sum+=i-x;
            int y=i-x;
            while (!a2.empty()&&a2.top().first>x){
                y+=a2.top().second;
                a2.pop();
            }
            a2.push(make_pair(x,y));
        }
    }
    cout<<sum<<endl;
    vector<int >m;
    while(!a2.empty()){
        m.push_back(a2.top().second);
        a2.pop();
    }
    cout<<m.size();
    for (int i = (int)m.size()-1; i >=0 ; --i) {
        cout<<" "<<m[i];

    }
    cout<<endl;
    return 0;
}

如果有更好的方法，欢迎交流和补充！！！