Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) B. Order Book | 书脊

Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) B. Order Book | 书脊
http://codeforces.com/contest/572/problem/B

In this task you need to process a set of stock exchange orders and use them to create order book.

An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number i has price pi, direction di — buy or sell, and integer qi. This means that the participant is ready to buy or sell qi stocks at price pi for one stock. A value qi is also known as a volume of an order.

All orders with the same price p and direction d are merged into one aggregated order with price p and direction d. The volume of such order is a sum of volumes of the initial orders.

An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.

An order book of depth s contains s best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than s aggregated orders for some direction then all of them will be in the final order book.

You are given n stock exhange orders. Your task is to print order book of depth s for these orders.

Input

The input starts with two positive integers n and s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50), the number of orders and the book depth.

Next n lines contains a letter di (either 'B' or 'S'), an integer pi (0 ≤ pi ≤ 105) and an integer qi (1 ≤ qi ≤ 104) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.

Output

Print no more than 2s lines with aggregated orders from order book of depth s. The output format for orders should be the same as in input.

Sample test(s)

input

6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10

output

S 50 8
S 40 1
B 25 10
B 20 4

Note

Denote (x, y) an order with price x and volume y. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.

You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.

题目大意: 对n个股票操作进行排序, 最后生成一个Order Book. 操作有两种, buy 和 sell, 后边是股票标号和价钱. 要求对相同操作的相同股票进行合并操作. 然后输出排序后前s个sell和buy的股票. 这里的排序要求是, 对于sell, 先对编号递增排序, 然后取前s (没有s个取所有). 然后再对编号递减排序. 对于buy直接递减排序即可.

---

分析: 用Java的TreeMap一下就出来了. 因为TreeMap本身就是有序的, 用Collections.reverseOrder()可以改变顺序. 然后取前s个的时候, 可以把set变成stream, 然后limit一下就可以

public void solve(int testNumber, InputReader in, OutputWriter out) {

        int n = in.readInt();

        int s = in.readInt();

        int cb = 0;

        int cs = 0;

        Map<Integer, Integer> BMap = new TreeMap<Integer, Integer>(Collections.reverseOrder());

        Map<Integer, Integer> SMap = new TreeMap<Integer, Integer>();

        for (int i = 0; i < n; i++) {

            String t = in.next();

            if (t.equals("B")) {

                Integer d = Integer.valueOf(in.next());

                Integer p = Integer.valueOf(in.next());

                if (BMap.containsKey(d))

                    BMap.put(d, BMap.get(d) + p);

                else

                    BMap.put(d,p);

                cb++;

            }

            else{

                Integer d = Integer.valueOf(in.next());

                Integer p = Integer.valueOf(in.next());

                if (SMap.containsKey(d))

                    SMap.put(d, SMap.get(d) + p);

                else

                    SMap.put(d,p);

                cs++;

            }

        }

        Stream<Map.Entry<Integer, Integer>> stream_s = SMap.entrySet().stream().limit(s).sorted(Map.Entry.comparingByKey(Collections.reverseOrder()));

 

        Stream<Map.Entry<Integer, Integer>> stream_b = BMap.entrySet().stream().limit(s);

 

        stream_s.forEach(ss -> out.printLine("S " + ss.getKey() + " " + ss.getValue()));

        stream_b.forEach(ss -> out.printLine("B " + ss.getKey() + " " + ss.getValue()));

 

    }

Read full article from Codeforces Round #317 [AimFund Thanks-Round] (Div. 2) B. Order Book | 书脊