CCF-201412-3（集合竞价）

一：问题描述

1.问题描述

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

2.输入格式

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

3.输出格式

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

4.样例输入

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

5.样例输出

9.00 450

6.评测用例规模与约定

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

二：理解

题解：
1.首先确定题意：让求开盘价和开盘成交量。
那么，开盘价是什么？？他是一个怎么样数？
开盘价只是一个价格而已（并不一定是两者都有的），他能决定买卖的各自的总股数，这是因为这两个量的计算方法是：
买单股数（出价至少为p0的买单的总股数）：就是大于等于开盘价的出手价的所有的股数；
卖单股数（出价至多为p0的卖单的总股数）：就是小于等于开盘价的出手价的所有的股数；

则此时的开盘成交量为：卖单股数和卖单股数的最小值；

而最终的开盘成交量为：最大的那一个。

如例子画图一样：

一共差不多可以分为四个成为成交量的可能：
①.当p0=100.00时，此时的开盘成交量为50。
②.当p0=9.00时，此时的开盘成交量为450。
③.当p0=8.92时，此时的开盘成交量为400。
④.当p0=8.88时，此时的开盘成交量为0。认为是没有意义的。

所以根据题意，最大的开盘成交量为450，此时的开盘价为9.00；

2.开盘价分析：

！！！开盘价一定是买价中的一个！！！

后面这些只是证明为什么开盘价要在买价中。

证明：
如果开盘价即在买价中，又在卖价中。
那开盘价已经是买价之一了。
如果开盘价p1只在卖价中。
那么在买价中找到与p1价格相差最小，却又比p1大的价格p2。（若找不到p2，p1比买价中的任意价格都要大，此时成交量为0，无意义，不考虑这种情况）当开盘价为p2时，买价中至少为开盘价的总股数与开盘价为p1时相等，卖价中至少为开盘价的总股数会大于或等于开盘价为p1时。所以当开盘价为p2时，成交量要么与开盘价是p1时相等，要么比p1时大。题目中说了，如果有多个符合条件的开盘价，应输出最大的价格，所以此时开盘价应选为p2，即开盘价不可能只在卖价中。
如果开盘价p1既不在买价中又不在卖价中。
我们先来定义一个概念，在买价和卖价中找到与p1价格相差最小，却又比p1大的价格，我称之为M价。那么p1会是M价减去0.01（精确到恰好小数点后两位），M价可能是买家、卖价或买卖价。当M价为买价时，开盘价为p1和开盘价为M价没有区别，买价至少为开盘价的总股数和卖价至少为开盘价的总股数都对应相等。当M价为卖价时或即在买价中又在卖价中，开盘价为M价的买价至少为开盘价的总股数与开盘价为p1是相等的，开盘价为M价的卖价至多为开盘价的总股数大于等于开盘价为p1时。题目中说了，如果有多个符合条件的开盘价，应输出最大的价格，所以此时开盘价应选为M价，这就又到了讨论M价的情况了（1、2、3再走一遍）。
第二条这个分析来自：
原文链接：https://blog.csdn.net/qq_36792042/article/details/82502890

三：代码

这个题的代码确实看不懂

代码一：
来自：https://www.cnblogs.com/xidian-mao/p/10501612.html

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;const int N=1e6+7;
const int M=5005;
struct node {bool by;  //标记是buy=1还是sell=0 int p; LL s;
}node[M]; 
bool flag[M];  //是否被撤销 
LL sum1[N], sum2[N];  //记录买卖成交量int main ()
{string str; int line=0; int p_max=0,p_min=0x3f3f3f3f;while (cin>>str) {line++;if (str[0]=='c') { int x; cin>>x; flag[x]=1; //将撤销标记位，置为1 }else {double p0;cin>>p0>>node[line].s; if (str[0]=='b') node[line].by=1;node[line].p=(int)(p0*100+0.5);  //将浮点型转化为整型； 必须加一个eps,否则浮点数运算会有误差p_max=max (p_max,node[line].p);p_min=min (p_min,node[line].p);}}int count=line; for (int i=1; i<=count; i++) if (!flag[i])  //未被撤销 {if (node[i].by)  //对应开盘价格 买单 sum1[node[i].p] += node[i].s;else   //卖单       sum2[node[i].p] += node[i].s;}for (int i=1;i<N;i++) {sum1[i]+=sum1[i-1];sum2[i]+=sum2[i-1];}LL sum=0; int ans;for (int i=p_max;i>=p_min;i--) {LL x = min(sum1[N-1]-sum1[i-1],sum2[i]);if (x>sum) { sum=x; ans=i; }}int a1=ans/100,a2=ans%100;printf("%d.%02d %lld\n",a1,a2,sum);return 0;
}

代码二：
这个是将买卖单进行不同的划分，分别vector来存储

#include<bits/stdc++.h>
#define N 5000
using namespace std;typedef long long ll;
struct Line{int index;//表示每行的行号double p;//表示每行的价格ll s;//表示每行的股数
}rb[N],rs[N];  //区分买卖单 
set<double> m; //set类似于vector 
int is[N];//这是用来判断是否取消操作int main()
{int b=0;  //记录buy的个数 int s=0;  //记录sell的个数 string name;//定义好操作名称int i=1;//开始标号 for(;cin>>name;){	if(name=="buy"){//此时表示是买单 cin>>rb[b].p>>rb[b].s;rb[b].index=i;  //行号更新 b++;i++;   }else if(name=="sell"){//此时表示是卖单cin>>rs[s].p>>rs[s].s;		rs[s].index=i;s++;i++;continue;}	else if(name=="cancel"){int num;cin>>num;is[num]=true;  //标记已删除 i++;}elsebreak;} m.clear();//清空m中的元素//将数据放入到vector中 for(int i=0;i<b;i++) if(is[rb[i].index]==false&&is[rs[i].index]==false){//在m的最后一个向量后插入两个个元素，其值为rb[x].p，rs[x].p m.insert(rb[i].p);m.insert(rs[i].p);}	double key=0;ll d=0;//通过迭代器方式读取set<double>::iterator it;for(it=m.begin();it!=m.end();it++) {ll s1=0,s2=0;for(int i=0;i<b;i++) if(*it<=rb[i].p&&(!is[rb[i].index])) s1+=rb[i].s;for(int j=0;j<s;j++) if(*it>=rs[j].p&&(!is[rs[j].index]))s2+=rs[j].s;ll v=min(s1,s2);if(v>=d){d=v;key=*it;  //类似于it[i]; }}printf("%.2lf %lld",key,d);return 0;
}

第二次做这个题：
自己写出来的代码：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long LL;
const int M = 5005;struct Node {int sign;   //标记买1卖0 int index;  //记录行号; double p;  //价格 LL s;  //成交量 
}node[M];
bool flag[M];  //标记是否被撤销1bool cmp(Node a, Node b)
{if(a.p == b.p)return a.sign > b.sign;elsereturn a.p > b.p;
}
int main()
{string str;int i = 1;  //记录行数int counts = 0;  //记录买卖单的个数for(; cin >> str; i++){if(str[0] == 'c'){int temp;cin >> temp;flag[temp] = 1;  //将其标记为已撤销 }else if(str[0] == 's' || str[0] == 'b') {cin >> node[counts].p >> node[counts].s;if(str[0] == 'b')	node[counts].sign = 1;node[counts++].index = i;}elsebreak;		}sort(node, node+counts, cmp);double max_p = 0;LL max_s = 0;for(int i=0; i<counts; i++){if(!flag[node[i].index] && node[i].sign){LL sell_count = 0;  //统计卖单for(int j=i; j<counts; j++){if(!node[j].sign && !flag[node[j].index])sell_count += node[j].s;}if(!sell_count)  //如果卖单为零，没有意义 continue;LL buy_count = 0;  //统计买单 for(int j=0; j<=i; j++){if(node[j].sign && !flag[node[j].index])buy_count += node[j].s;}LL temp_count = min(buy_count, sell_count);  //选出最下的成交量 if(temp_count > max_s)  //比较最大的成交量 {max_p = node[i].p;max_s = temp_count;}}}printf("%.2lf %lld\n",max_p,max_s);return 0;
}