[CFF认证]201412-3集合竞价（C++）

问题描述

试题编号：	201412-3
试题名称：	集合竞价
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。　　该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：　　1. buy p s 表示一个购买股票的买单，每手出价为p，购买股数为s。　　2. sell p s 表示一个出售股票的卖单，每手出价为p，出售股数为s。　　3. cancel i表示撤销第i行的记录。　　如果开盘价为p ₀，则系统可以将所有出价至少为p ₀的买单和所有出价至多为p ₀的卖单进行匹配。因此，此时的开盘成交量为出价至少为p ₀的买单的总股数和所有出价至多为p ₀的卖单的总股数之间的较小值。　　你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。输入格式　　输入数据有任意多行，每一行是一条记录。保证输入合法。股数为不超过10 ⁸的正整数，出价为精确到恰好小数点后两位的正实数，且不超过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。

答案：一上午加半个下午，终于把这道题搞清楚了。一开始忽略了题目中的股数为不超过10⁸的正整数，所以在计算买家总销量，卖家总销量和成交价时，用int类型会有可能产生溢出的情况，所以一开始用int一直是80分，还找不到错误，后来改成long long就好了，以后要认真读题，注意溢出情况。

根据题意，开盘价一定是买家的价格之一：

证明：1. 如果开盘价即在买家中，又在卖家中，那开盘价已经是买家价格之一了。

2. 如果开盘价p1只在卖家中，没有在买家中，那么在买家中找到与p1价格相差最小却又比p1大的价格p2。（若找不到p2，p1比买家中的任意价格都要大，此时成交价格为0，无意义，不考虑这种情况）当开盘价为p2时，买家中的总销量与开盘价为p1时相等，卖家中的总销量大于或者等于开盘价为p1时的总销量（因为p2大于p1，且距离p1最近，所以对于买家中的总销量是没有影响的，对于卖家中的总销量，如果卖家中存在大于p1小于p2的价格时，总销量还会增大，否则不变）。所以当开盘价为p2时，成交量要么与p1时相等，要么比p1时大。由于题目中说了，如果有多个符合条件的开盘价，应输出最大的价格，所以此时开盘价应选为p2，即开盘价不可能只在卖家中。

3.如果开盘价p1既不在买家中又不在卖家中，同理在买家中找到与p1相差最小价格大于p1的价格p2。同样可证明p2应为开盘价，证明方式同2。

#include <windows.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
struct stock{
	int enable;
	string mm;
	double price;
	int num;
	stock(int a, string b, double c, int d) :enable(a), mm(b), price(c), num(d){}
};
int main(){
	vector<stock> v;
	while (1){
		string s;
		cin >> s;
        if (s == "buy" || s == "sell"){
			double p;
			int n;
			cin >> p >> n;
			stock* tem = new stock(1, s, p, n);
			v.push_back(*tem);
		}
		else if (s == "cancel"){
			int line;
			cin >> line;
			stock* tem = new stock(0, "cancel", 0, line);
			v.push_back(*tem);
			v[line - 1].enable = 0;
		}
		else
			break;
	}//输入部分结束
	set<double> Price;
	for (int i = 0; i < v.size(); i++)
		if (v[i].enable == 1&&v[i].mm=="buy")
			Price.insert(v[i].price);
	set<double>::iterator ite = Price.begin();//用一个set存储买家中的价格，此处用了set的自动排序功能，保证输出的成交价是符合条件的成交价中最高的。
	double perPrice=0;
	long long sumStock=0;
	while (ite != Price.end()){
		double p = *ite;
		long long sumBuy = 0;
		long long sumSell = 0;
		for (int i = 0; i < v.size(); i++){
			if (v[i].enable == 1){
				if (v[i].mm == "buy"&&v[i].price>=p) sumBuy += v[i].num;
				if (v[i].mm == "sell"&&v[i].price<=p) sumSell += v[i].num;
			}
		}
		long long sumBS = (sumBuy>sumSell) ? sumSell : sumBuy;
		if (sumStock <= sumBS){
			sumStock = sumBS;
			perPrice = p;
		}
		ite++;
	}
	printf("%.2f ", perPrice);
	cout << sumStock << endl;
	return 0;
}

秒客网

[CFF认证]201412-3集合竞价（C++）

相关文章