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.math.BigInteger;
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();
    }
}

// Fast reader for ACM By Azure99
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 nextLine() {
        tokenizer = new StringTokenizer("");
        return innerNextLine();
    }

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

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

    public double nextDouble() {
        return Double.valueOf(next());
    }

    public BigInteger nextBigInteger() {
        return new BigInteger(next());
    }

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

// Fast writer for ACM By Azure99
class AWriter implements Closeable {
    private BufferedWriter writer;

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

    public void print(Object object) throws IOException {
        writer.write(object.toString());
    }

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

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

Azure99

大二蒟蒻,喜欢折腾vps、玩机,偶尔写写代码

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注