CCF CSP 201412-3 集合竞价

问题描述

　　某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
　　该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：
　　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、2、3、4分别卖出10、10、10、10，那么在开盘价为1、2、3、4时，分别能成交10、20、30、40。故成交量是一个累积函数。对于买入操作也是一个累积函数，不过是从最高价往最低价累积。

首先对所有的卖出操作排序，计算价格为所有操作价格的累积卖出量及累积买入量。二者取最小值，就是开盘价为此价格时的成交量。

题意需要注意的是：cancel i表示撤销第i行的记录。而不是撤销第i条合法操作。

排序的时候首先根据价格排序，价格相同时应该让sell在buy之前。

代码

C++

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct Tran {
    int t; // 0:sell, 1:buy, 2:cancel
    double p;
    int s;
    Tran(bool t_, double p_, int s_) : t(t_), p(p_), s(s_) {}
    bool operator<(const Tran &other) const {
        if(p < other.p) return true;
        else if(p == other.p && t < other.t) return true;
        return false;
    }
};

int main() {
    string t;
    double p;
    int s;
    int id;
    vector<Tran> trans;
    while(cin >> t) {
        if(t == "buy") {
            cin >> p >> s;
            trans.push_back(Tran(1, p, s));
        }
        else if(t == "sell") {
            cin >> p >> s;
            trans.push_back(Tran(0, p, s));
        }
        else if(t == "cancel") {
            cin >> id;
            trans[id-1].s = 0;
            trans.push_back(Tran(2, 0, 0));
        }
    }
    sort(trans.begin(), trans.end());
    vector<long long> sellCum(trans.size()), buyCum(trans.size());
    long long cum = 0;
    for(int i=0; i<trans.size(); i++) {
        if(trans[i].t==0) {
            cum += trans[i].s;
        }
        sellCum[i] = cum;
    }
    cum = 0;
    for(int i=trans.size()-1; i>=0; i--) {
        if(trans[i].t==1) {
            cum += trans[i].s;
        }
        buyCum[i] = cum;
    }
    double bestP;
    long long bestS = 0;
    
    for(int i=0; i<trans.size(); i++) {
        long long s = min(sellCum[i], buyCum[i]);
        if(s >= bestS) {
            bestP = trans[i].p;
            bestS = s;
        }
    }
    printf("%.2lf %lld", bestP, bestS);
}