CCF CSP 201412-3.集合竞价

发表于 | 更新于 | 分类于 | 浏览 次
字数统计: 1.7k

问题描述

　　某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
　　该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：
　　1. buy p s 表示一个购买股票的买单，每手出价为p，购买股数为s。
　　2. sell p s 表示一个出售股票的卖单，每手出价为p，出售股数为s。
　　3. cancel i表示撤销第i行的记录。
如果开盘价为p0，则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。因此，此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。
　　你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。

输入格式

　　输入数据有任意多行，每一行是一条记录。保证输入合法。股数为不超过$10^8$的正整数，出价为精确到恰好小数点后两位的正实数，且不超过10000.00。

输出格式

　　你需要输出一行，包含两个数，以一个空格分隔。第一个数是开盘价，第二个是此开盘价下的成交量。开盘价需要精确到小数点后恰好两位。

样例输入

buy 9.25 100
buy 8.88 175
sell 9.00 1000
buy 9.00 400
sell 8.92 400
cancel 1
buy 100.00 50

样例输出

9.00 450

评测用例规模与约定

　　对于100%的数据，输入的行数不超过5000。

分析：

定义类（结构体）表示每行的交易记录

1
2
3
4
5
6
7
8
9
10
typedef struct Node {
	// 交易类型，0-buy,1-sell,2-cancel
	int type;
	// 出价
	float price;
	// 交易的股数
	int amount;
	// 交易是否被取消
	bool cancel;
} Transaction;

用vector<Transaction>（Java中用List<Transaction>）存储输入的所有交易记录。

按照交易记录的类型，分为买单和卖单。买单和卖单均按照价格从小到大的顺序排列。

设使得成交量最大的开盘价为price，最大成交量为maxAmount，二者均初始化为0。

遍历所有的买单（开盘价一定会在买单中出现，证明见2），以当前交易的出价p为开盘价，计算成交量dealAmount。

若dealAmount > maxAmount 或者 dealAmount == maxAmount && p > price，则更新price和maxAmount。

1.成交量最高将达到$2500 \times 10^8 = 2.5 \times 10^{11}​$，超出了int的存储范围。

因此，在C++中，成交量、买单和卖单的总股数，要用long long存储；Java中使用long存储。

2.开盘价p0一定会在买单中出现。

证明：（反证法）假设开盘价p0只在卖单中出现：

设出价至少为p0的买单的总股数为s1，出价至多为p0的卖单的总股数为s2。

此时的成交量$sale0 = min(s1,s2)$

$\exists p \in 买单, 使得p \gt p0成立$，$p1 = \min p \gt p0$。

设出价至少为p1的买单的总股数为s3，出价至多为p1的卖单的总股数为s4。

从而，$s1 =s3,s2 \le s4 $ ,

$sale1=min(s1,s4) \ge sale0$，应选择p1为开盘价，这与假设矛盾。

故，开盘价一定会在买单中出现。

  • C++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct Node {
	// 交易类型，0-buy,1-sell,2-cancel
	int type;
	// 出价
	float price;
	// 交易的股数
	int amount;
	// 交易是否被取消
	bool cancel;
} Transaction;

bool cmp(Transaction a, Transaction b) {
	return a.price < b.price;
}

int main() {
	char status[7];
	vector<Transaction> arr;

	while (scanf("%s", status) != EOF) {
		Transaction t;
		// 若为撤销
		if (strcmp(status, "cancel") == 0) {
			int line;
			scanf("%d", &line);

			t.type = 2;
			t.cancel = true;
			arr.push_back(t);

			// 撤销第line行的交易记录
			arr[line - 1].cancel = true;
			continue;
		}

		if (strcmp(status, "buy") == 0) {
			// 若为买单
			t.type = 0;
		} else {
			// 若为卖单
			t.type = 1;
		}
		t.cancel = false;
		scanf("%f %d", &t.price, &t.amount);
		arr.push_back(t);
	}

	// 分割为买单和卖单
	vector<Transaction> buys;
	vector<Transaction> sells;
	for (int i = 0; i < arr.size(); i++) {
		// 忽略被撤销的交易记录（或者撤销命令本身）
		if (arr[i].cancel) {
			continue;
		}
		if (arr[i].type == 0) {
			buys.push_back(arr[i]);
		} else {
			sells.push_back(arr[i]);
		}
	}

	// 按照价格从小到大排序
	sort(buys.begin(), buys.end(), cmp);
	sort(sells.begin(), sells.end(), cmp);

	// 开盘价
	float price;
	// 最大成交量
	long long maxAmount = 0;
	for (int i = 0; i < buys.size(); i++) {
		Transaction t = buys[i];

		long long buyAmount = 0, sellAmount = 0;
		for (int j = i; j < buys.size(); j++) {
			buyAmount += buys[j].amount;
		}
		for (int j = 0; j < sells.size() && sells[j].price <= t.price; j++) {
			sellAmount += sells[j].amount;
		}
		long long dealAmount = min(buyAmount, sellAmount);
		// 选择最大的成交量；若成交量相等，则选择最高的开盘价
		if ((dealAmount > maxAmount)
				|| (dealAmount == maxAmount && t.price > price)) {
			maxAmount = dealAmount;
			price = t.price;
		}
	}
	printf("%.2f %lld\n", price, maxAmount);
	return 0;
}
  • Java版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	static class Transaction implements Comparable<Transaction> {
		// 交易类型，0-buy,1-sell,2-cancel
		int type;
		// 出价
		double price;
		// 交易的股数
		long amount;
		// 交易是否被取消
		boolean cancel;

		@Override
		public int compareTo(Transaction o) {
			if (this.price > o.price) {
				return 1;
			}
			if (this.price == o.price) {
				return 0;
			}
			return -1;
		}

	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		List<Transaction> list = new ArrayList<>();
		while (scan.hasNextLine()) {
			String line = scan.nextLine();
			String[] sArr = line.split(" ");
			Transaction t = new Transaction();

			// 若为撤销
			if ("cancel".equals(sArr[0])) {
				t.type = 2;
				t.cancel = true;
				list.add(t);

				// 撤销第index行的交易记录
				int index = Integer.parseInt(sArr[1]);
				list.get(index - 1).cancel = true;
				continue;
			}

			// 若为买单
			if ("buy".equals(sArr[0])) {
				t.type = 0;
			} else { // 若为卖单
				t.type = 1;
			}
			t.price = Float.parseFloat(sArr[1]);
			t.amount = Long.parseLong(sArr[2]);
			list.add(t);
		}
		scan.close();

		// 分割为买单和卖单
		List<Transaction> buys = new ArrayList<>(list.size());
		List<Transaction> sells = new ArrayList<>(list.size());
		for (Transaction t : list) {
			// 忽略被撤销的交易记录（或者撤销命令本身）
			if (t.cancel) {
				continue;
			}
			if (t.type == 0) {
				buys.add(t);
			} else {
				sells.add(t);
			}
		}

		// 按照价格从小到大排序
		Collections.sort(buys);
		Collections.sort(sells);

		long maxAmount = 0L;
		double price = 0d;
		for (int i = 0; i < buys.size(); i++) {
			Transaction t = buys.get(i);
			long buyAmount = 0L, sellAmount = 0L;
			for (int j = i; j < buys.size(); j++) {
				buyAmount += buys.get(j).amount;
			}
			for (Transaction t2 : sells) {
				// 出价最多为t.price
				if (t2.price > t.price) {
					break;
				}
				sellAmount += t2.amount;
			}
			long dealAmount = Math.min(buyAmount, sellAmount);
			// 选择最大的成交量；若成交量相等，则选择最高的开盘价
			if (maxAmount < dealAmount || (maxAmount == dealAmount && price < t.price)) {
				maxAmount = dealAmount;
				price = t.price;
			}
		}

		System.out.printf("%.2f %d\n", price, maxAmount);
	}
}

----------本文结束感谢您的阅读----------
坚持原创技术分享，您的支持将鼓励我继续创作！