CF572B Order Book 题解

Content

账单里面有 \(n\) 条记录，只有卖出记录和买入记录两种，并且都包含两个信息 \(p_i,q_i\)，现在根据这些记录，请执行如下操作：

将所有 \(p_i\) 相等的同种记录合并（就是只能卖出记录和卖出记录合并，买入记录和买入记录合并，不能将卖出记录和买入记录合并）。
合并之后，将所有 \(p_i\) 最小的 \(s\) 条卖出记录按照 \(p_i\) 降序输出。将所有 \(p_i\) 最大的 \(s\) 条买入记录按照 \(p_i\) 降序输出。

笔者提醒：买入卖出记录可能不足 \(s\) 条，这时将所有的记录按照 \(p_i\) 降序输出。

数据范围：\(1\leqslant n\leqslant1000,1\leqslant s\leqslant 50,0\leqslant p_i\leqslant 10^5,1\leqslant q_i\leqslant 10^4\)。

Solution

\(n\) 很小，所以我们考虑直接 \(\mathcal{O}(n^2)\) 遍历，看前面是否有 \(p_i\) 和当前的 \(p_i\) 相等，有的话直接合并，否则新开一个存储。然后卖出记录按照从小到大排序后倒序输出，买入记录按照从大到小排序后正序输出即可。

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

using namespace std;

int n, s, socnt, bucnt, visso[100007], visbu[100007];

struct node {

	int x, y;

	bool operator < (const node& cjy) const {return x < cjy.x;}

}so[1007];

struct node2 {

	int x, y;

	bool operator < (const node2& cjy) const {return x > cjy.x;}

}bu[1007];

int main() {

	scanf("%d%d", &n, &s);

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

		char opt[2]; int p, q;

		scanf("%s%d%d", opt, &p, &q);

		if(opt[0] == 'B') {

			if(visbu[p]) {

				for(int j = 1; j <= bucnt; ++j)

					if(bu[j].x == p) {

						bu[j].y += q;

						break;

					}

			}

			else {

				bu[++bucnt] = (node2){p, q};

				visbu[p] = 1;

			}

		} else {

			if(visso[p]) {

				for(int j = 1; j <= socnt; ++j)

					if(so[j].x == p) {

						so[j].y += q;

						break;

					}

			}

			else {

				so[++socnt] = (node){p, q};

				visso[p] = 1;

			}

		}

	}

	sort(so + 1, so + socnt + 1);

	sort(bu + 1, bu + bucnt + 1);

	for(int i = min(socnt, s); i >= 1; --i)

		printf("S %d %d\n", so[i].x, so[i].y);

	for(int i = 1; i <= min(bucnt, s); ++i)

		printf("B %d %d\n", bu[i].x, bu[i].y);

	return 0;

}

巴特西

CF572B Order Book 题解

Content

Solution

Code

最新文章

热门文章