SDNUOJ-1296-PPMM(模拟队列-优化)

题目

题目链接

Description
 假设这里有一个队列，我们可以对其进行下述操作：
 PUSH X：意味着将一个整数X（-2^31＜X＜2^31）加入到队尾。
 POP：从队头删除一个数，如果队列为空则不进行操作。
 MINUS：将队列中所有的数字变成其相反数。
 MAX：输出队列中所有数字的最大值，如果队列为空则不进行输出。

Input
 第一行包括一个整数T（T≤10），表示接下来有T组测试数据。对于每一组测试数据，第一行包括一个数N（N≤2000000），表示操作次数，接下来的N行给出具体操作。
Output
 对于每一组数据，在新的一行输出MAX返回的数。每组测试数据之间输出一个空行。

样例

Sample Input
1
6
PUSH -2
MINUS
PUSH -1
MAX
POP
MAX
Sample Output
2
-1

题目分析

题意

很简单，就是自己模拟一个队列，有入队，出队，但是，还要求最大值，取反。暴力实现MAX、MINUS肯定是不行的，所以难点就在于如何优化。

思路

MINUS优化可以用两个数组，每MINUS一次就改变一次输入的数组，另一个数组输入相反数。

MAX优化用两个变量保存数组1的最大值和最小值，输出的时候判断当前操作的数组，输出MAX或-MIN。

POP时需要判断一下，如果当前的MAX或MIN出队了，就需要重新遍历数组，找出新的MAX或MIN。

注意，此题使用了我个人的Java快速IO模板。

代码

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        AReader reader = new AReader(new BufferedInputStream(System.in));
        AWriter writer = new AWriter(System.out);

        int T = reader.nextInt();
        int[] arr;
        while (T-- > 0) {
            int N = reader.nextInt();

            arr = new int[N];
            int sIndex = 0;
            int eIndex = 0;
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            boolean negative = false;

            while (N-- > 0) {
                String operStr = reader.next();

                char oper = operStr.charAt(1);
                switch (oper) {
                    case 'U'://PUSH
                        int num = reader.nextInt();

                        if (!negative) {
                            arr[eIndex] = num;
                        } else {
                            arr[eIndex] = -num;
                        }

                        if (arr[eIndex] > max || sIndex == eIndex) {
                            max = arr[eIndex];
                        }
                        if (arr[eIndex] < min || sIndex == eIndex) {
                            min = arr[eIndex];
                        }

                        eIndex++;

                        break;
                    case 'O'://POP
                        if (sIndex == eIndex) {
                            break;
                        }
                        sIndex++;

                        if (arr[sIndex - 1] == max) {
                            max = Integer.MIN_VALUE;
                            for (int i = sIndex; i < eIndex; i++) {
                                if (arr[i] > max) {
                                    max = arr[i];
                                }
                            }
                        }

                        if (arr[sIndex - 1] == min) {
                            min = Integer.MAX_VALUE;
                            for (int i = sIndex; i < eIndex; i++) {
                                if (arr[i] < min) {
                                    min = arr[i];
                                }
                            }
                        }

                        break;
                    case 'I'://MINUS
                        negative = !negative;

                        break;
                    case 'A'://MAX
                        if (sIndex == eIndex) {
                            break;
                        }
                        if (!negative) {
                            writer.println(max);
                        } else {
                            writer.println(-min);
                        }

                        break;
                }
            }
            writer.println("");
        }

        reader.close();
        writer.close();
    }
}

class AReader implements Closeable {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public AReader(InputStream inputStream) {
        reader = new BufferedReader(new InputStreamReader(inputStream));
        tokenizer = new StringTokenizer("");
    }

    private String innerNextLine() {
        try {
            return reader.readLine();
        } catch (IOException ex) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!tokenizer.hasMoreTokens()) {
            String nextLine = innerNextLine();
            if (nextLine == null) {
                return false;
            }
            tokenizer = new StringTokenizer(nextLine);
        }
        return true;
    }

    public String next() {
        hasNext();
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    @Override
    public void close() throws IOException {
        reader.close();
    }
}

class AWriter implements Closeable {
    private BufferedWriter writer;

    public AWriter(OutputStream outputStream) {
        writer = new BufferedWriter(new OutputStreamWriter(outputStream));
    }

    public void println(Object object) throws IOException {
        writer.write(object.toString());
        writer.write("\n");
    }

    @Override
    public void close() throws IOException {
        writer.close();
    }
}