By

问题描述

　　某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
　　该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：
　　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。

题目解析

一开始的时候，没有想清楚这个cancel的含义是什么，以为它只是把它所说的那行取消了。没有注意到其实它自己本身也算是一行，提交了只有30分。后来发现之后，把cancel输入的那行数据也改成无效数据，就有80分。剩下的20分其实是因为把成交量定义成了int，int的长度不够保存，于是把它改成long long之后提交，就有100分了。具体解释在代码里注释的非常清楚了。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
//使用Money来存储所有输入的命令 
struct Money{
    float cost;//价格 
    long long count;//股数 
    char type;//0为不存在，1为buy，2为sell
};

bool cmp(const Money &m1,const Money &m2){
    return m1.cost<m2.cost;
}

int main(){
    string str;
    Money money[5010];
    int n=0;
    while(cin>>str){//先接收buy,sell,cancel命令 
        //if(str=="00") break;
        if(str=="cancel"){//如果是cancel命令，num行数据无效，cancel行数据无效 
            int num;
            cin>>num;
            money[num-1].type=0;
            money[num-1].cost=0;
            money[num-1].count=0;
            money[n].type=0;
            money[n].cost=0;
            money[n].count=0;
            n++;
        }
        else if(str=="buy"){//接收buy命令 
            float costf;
            long long counti;
            cin>>costf>>counti;
            money[n].type=1;
            money[n].cost=costf;
            money[n].count=counti;
            n++;
        }
        else if(str=="sell"){//接收sell命令 
            float costf;
            long long counti;
            cin>>costf>>counti;
            money[n].type=2;
            money[n].cost=costf;
            money[n].count=counti;
            n++;
        }
    }
    
    //对结构体进行排序，根据股价从小到大排序 
    sort(money,money+n,cmp);
    float qcost=0;//最后确定的股价 
    long long qcount=0;//最后确定的成交量 
    int can=0;//因为经过了排序，所有的无效数据都被排到最前面，用can来标记第一个有效数据的下标 
    
    //主循环 
    for(int i=0;i<n;i++){
        //循环前面阶段用来计算can的值 ，即无效数据有多少 
        if(!money[i].type) {
            can++;
            continue;
        } 
        //下面是关键代码 
        else{
            //从can开始遍历整个结构体 ，令zcost为暂时的成交价格 
            float zcost=money[i].cost;
            long long allcount=0,countbuy=0,countsell=0;//allcount为暂时的成交量 
            for(int k=can;k<n;k++){//再从can开始进行结构体的全遍历 
                if(money[k].cost<=zcost&&money[k].type==2){//sell类型，股价不高于暂时的成交价格 
                    countsell+=money[k].count;
                }
                if(money[k].cost>=zcost&&money[k].type==1){//buy类型，估计不低于 暂时的成交价格 
                    countbuy+=money[k].count;
                }
            }
            allcount=min(countbuy,countsell);//依题意在buy和sell类型的成交价格中取较小值 
            if(allcount>=qcount){//如果暂时的成交量比现有的最大成交量大，替换现有的最大成交量 
                qcount=allcount;
                qcost=zcost;
            }
        }
    }
    printf("%.2f ",qcost);
    cout<<qcount<<endl;
    return 0;
}