ccf 集合竞价

问题描述

试题编号：	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。

//模拟
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 struct node
 8 {
 9      string s;
10     double a;
11      long long b;
12 };
13 node n[5007],n1[5007],n2[5007];
14 bool flag[5007];
15 int num,num1,num2;
16 long long ans_num;
17 double ans_price;
18 bool cmp1(node n11,node n22)
19 {
20     if(n11.a!=n22.a) return n11.a<n22.a;
21     else if(n11.a==n22.a)
22     {
23         return n11.b>=n22.b;}
24 }
25 bool cmp2(node n11,node n22)
26 {
27     if(n11.a!=n22.a) return n11.a>n22.a;
28     else if(n11.a==n22.a) return n11.b>=n22.b;
29 }
30 void slove()
31 {
32     long long sum1=0,sum2=0;double price;
33     int j=0;
34     for(int i=0;i<num1;i++)
35     {
36         price=n1[i].a;
37         sum1+=n1[i].b;
38         sum2=0;
39         for(int j=0;j<num2;j++){
40             if(n2[j].a>price) break;
41             sum2+=n2[j].b;
42         }
43         if(ans_num<min(sum1,sum2)){
44             ans_num=min(sum1,sum2);
45             ans_price=price;
46         }
47     }
48 }
49 
50 int main()
51 {
52    //  freopen("in.txt","r",stdin);
53     num=1;
54     memset(flag,1,sizeof(flag));
55     while(cin>>n[num].s){
56         if(n[num].s=="buy"||n[num].s=="sell"){
57             scanf("%lf%lld",&n[num].a,&n[num].b);
58             num++;
59         }
60         else if(n[num].s=="cancel"){
61             scanf("%lld",&n[num].b);
62             num++;
63         }
64     }
65     for(int i=num-1;i>=1;i--)
66     {
67         if(n[i].s=="cancel"){
68             flag[n[i].b]=1-flag[n[i].b];
69         }
70     }
71     num1=0;num2=0;
72     for(int i=1;i<num;i++)
73     {
74         if(flag[i]){
75             if(n[i].s=="buy"){
76                 n1[num1].a=n[i].a;
77                 n1[num1++].b=n[i].b;
78             }
79             else  if(n[i].s=="sell"){
80                 n2[num2].a=n[i].a;
81                 n2[num2++].b=n[i].b;
82             }
83         }
84     }
85     sort(n1,n1+num1,cmp2);
86     sort(n2,n2+num2,cmp1);
87     slove();
88     printf("%.2lf %lld
",ans_price,ans_num);
89     return 0;
90 }