Areas on the Cross-Section Diagram（计算面积）

题目链接： http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D

Your task is to simulate a flood damage.

For a given cross-section diagram, reports areas of flooded sections.

Assume that rain is falling endlessly in the region and the water overflowing from the region is falling in the sea at the both sides. For example, for the above cross-section diagram, the rain will create floods which have areas of 4, 2, 1, 19 and 9 respectively.

Input

A string, which represents slopes and flatlands by '/', '' and '_' respectively, is given in a line. For example, the region of the above example is given by a string "///_//\/////__\_//_/".

output

Report the areas of floods in the following format:

(A)

$k quad L_1 quad L_2 quad ... quad L_k $

In the first line, print the total area A of created floods.

In the second line, print the number of floods k and areas Li(i=1,2,...,k) for each flood from the left side of the cross-section diagram. Print a space character before Li.

Constraints

1≤ length of the string ≤20,000

Sample Input 1

//

Sample Output 1

4

1 4

Sample Input 2

///_//\/////__\_//_/

Sample Output 2

35

5 4 2 1 19 9

这道题主要是对栈这种数据结构进行应用，我们使用java中的集合类ArrayDeque来实现。

首先，我们先求总面积。对输入的每个字符进行检查，当碰到""时，我们将其压入栈（压入栈的是其对应的位置）；当碰到"_"时，不做任何处理；当碰到"/"时，检查栈是否为空，不为空就说明有对应的"/"，弹出栈顶元素，用当前的位置减去弹出的栈顶元素，累加这些差值就是最后的面积了。

然后，对于每一个积水处的面积，我们也使用了栈，栈中存放的对象为两个元素组合的类，两个元素分别为位置和面积。位置定义为某个积水处的起始处，面积定义为这个积水处的面积。因为我们是从前向后遍历字符，所以每个积水处的面积不能一下子求出来，为此我们采取的措施为先将目前已知的积水处压入栈，对于下一个要压入栈的积水处，检查已压入栈的元素是否包含在这个要压入的积水处，如果包含，则将积水处合并，如果不包含，则直接压入栈即可。

参考代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

class Pair{
    int position;
    int area;

    Pair(int pos, int area){
        this.position = pos;
        this.area = area;
    }
}

public class AreasCrossSectionDiagram {

    public static void main(String[] args) throws IOException {

        int sum = 0;
        ArrayDeque<Integer> stack1 = new ArrayDeque<>();
        ArrayDeque<Pair> stack2 = new ArrayDeque<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String string = br.readLine();
        char[] chars = string.toCharArray();
        for (int i=0; i<chars.length; i++){
            if (chars[i] == '\'){
                stack1.push(i);
            }
            else if (chars[i] == '/' && !stack1.isEmpty()){
                int j = stack1.pop();
                int temp = i-j;
                sum += temp;
                while (!stack2.isEmpty() && stack2.peek().position>j){
                    temp += stack2.pop().area;
                }
                stack2.push(new Pair(j, temp));
            }
        }

        // 将stack2反转
        ArrayDeque<Integer> stack3 = new ArrayDeque<>();
        while (!stack2.isEmpty()){
            stack3.push(stack2.pop().area);
        }

        System.out.println(sum);
        System.out.print(stack3.size());

        while (!stack3.isEmpty()){
            System.out.print(" " + stack3.pop());
        }
        System.out.println();
    }
}

参考文献：《挑战程序设计竞赛-算法和数据结构》