CCF CSP 201412-3 集合竞价

发表于 | 分类于 ，
字数统计: 1.3k | 阅读时长 ≈ 5

CCF CSP 201412-3 集合竞价

♔问题描述

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

♔输入格式

输入数据有任意多行，每一行是一条记录。保证输入合法。股数为不超过108的正整数，出价为精确到恰好小数点后两位的正实数，且不超过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。

♔解题思路

​ 根据题意可知，我们要求的是使成交量最大的最高的价格，借鉴博客的证明可知开盘价一定是输入的p中。为什么呢，将测试案例按p从小到大排列开，如下图所示。图示中各价格用序号标识好，方便说明。

img

​ （下述最优解意思是可以取到最大开盘价的解）

​ 假设(8.92,9.00)区间（注意是开区间）内某一点p是最优价格，那么大于或等于这个价格的buy点有3、5，小于等于它的sell点有2，那么不管p在区间(8.92,9.00)内怎么浮动，都不影响大于它的sell点和小于它的buy点的选择，都是点2和点3、5。题目要求取最大值，所以在假设在(2,3)区间存在最优价格的情况下，取值可以无限逼近与9.00。

​ 当价格9.00存在sell点时，值取到9.00显然不会改变原有的buy、sell点的选择。

​ 当9.00存在sell点时，取9.00将会影响buy、sell点的选择。在趋于9.00时，设sell的总股数为a，buy的总股数为b。取到9.00时.设sell的总股数为a+c，buy的总股数为b，很容易明白min(a,b) <= min(a+c,b)，即在9.00存在sell点时，得到的结果总会优于趋近于9.00却没有取9.00上的sell点的情况。推广开来，我们可以知道，假设两个点的区间(a,b]上存在最优解，那么b一定也是最优解，且b是最大的，所以b是答案。所以答案一定是存在于已知的点上 。

​ （又及，十年oi一场空，不开long long见祖宗

♔代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
#include<sstream>
#include<string>
#define ll long long
using namespace std;
struct data
{
	ll sum,flag;
	double price; 
}tic[5005];
string a;
ll n,alls,allb,maxs;
double maxp;

int wly(data a,data b)
{
	if(a.price>b.price) return 1;
	if(a.price==b.price && a.flag<b.flag) return 1;
	return 0;
}

int main()
{
	int i,j;
	i=1;n=0;
	while(cin>>a)
	{	
		if(a=="buy")
		{
			cin>>tic[i].price;
			cin>>tic[i].sum;
			tic[i].flag=0;
		}
		else if(a=="sell")
		{
			cin>>tic[i].price;
			cin>>tic[i].sum;
			tic[i].flag=1;
		}
		else if(a=="cancel")
		{
			cin>>j;
			tic[j].price=0.0;
			tic[j].sum=0;
			n--;
		}
		i++;n++;
	}
	n--;
	sort(tic+1,tic+i,wly);
	//printf("%d %d\n",i,n);
	//for(i=1;i<=n;i++) 
	//	printf("%d %lf %d\n",tic[i].sum,tic[i].price,tic[i].flag);
	j=n;
	for(i=2;i<=j;i++)	
	{
		if(tic[i].price==tic[i-1].price && tic[i].flag==tic[i-1].flag)
		{
			tic[i].sum+=tic[i-1].sum;
			tic[i-1].flag=0;tic[i-1].price=0.0;tic[i-1].flag=0;
			n--;
		}
	} 
	sort(tic+1,tic+i,wly);
	for(i=1;i<=n;i++) alls+=tic[i].flag*tic[i].sum;
	for(i=1;i<=n;i++)
	{
		//printf("-%d %d-\n",alls,allb);
		if(tic[i].flag)
		{
			alls-=tic[i].sum;
			continue;
		}
		allb+=tic[i].sum;
		if(maxs<min(alls,allb))
		{
			maxs=min(alls,allb);
			maxp=tic[i].price;
		}
	}
	//for(i=1;i<=n;i++) 
	//	printf("%d %lf %d\n",tic[i].sum,tic[i].price,tic[i].flag);
	printf("%.2lf %lld",maxp,maxs);
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！