股票开盘的最大成交额-----一道不错的贪心算法题目

 

---

问题如下：

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

---

源码：

#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

const int MIN = 0;

typedef struct Shares{
    //买或卖的价格
    double price;
    //股数
    int number;
    //false 表示买
    //true 表示卖
    bool buyOrSell;
    //是否被cancel
    bool enable;
    Shares()
    {
        price = 0.00;
        number = 0;
        buyOrSell = false;
        enable = true;
    }
};
int min(int num1, int num2);
//取消的第th条交易股
void cancelRecord(int th);
//从未分类的交易股，按照条件进行分类存储，并进行排序
void divTypeOfShares(int n, int &lenOfSell, int& lenOfBuy);
//计算结果
void computePriceAndMax(int n, double& perPrice, int& perNumber);


//存储输入的交易股，不区分买家还是卖家
Shares shares[10001];
//存储买家的交易股
Shares sharesBuy[5001];
//存储卖家的交易股
Shares sharesSell[5001];



//定义买家类型的交易股比较函数，用于排序
//主排序按照价格为关键字递增
//次排序按照购买股数作为关键字递减
bool cmpBuy(Shares buy1, Shares buy2)
{
    if (buy1.price != buy2.price)
        return buy1.price < buy2.price;
    else if (buy1.price == buy2.price)
        return buy1.number >= buy2.number;
}

//卖家类型的交易股同上
bool cmpSell(Shares sell1, Shares sell2)
{
    if (sell1.price != sell2.price)
        return sell1.price >= sell2.price;
    else if (sell1.price == sell2.price)
        return sell1.number >= sell2.number;
}



void main(void)
{
    char typeOfShares[10];
    double price;
    int number;
    int index = 1;

    double perPrice = 0.00;
    int perNumber = MIN;
    while (cin >> typeOfShares)
    {

        if (strcmp(typeOfShares, "buy") == 0)
        {
            cin >> price >> number;
            shares[index].buyOrSell = false;
            shares[index].price = price;
            shares[index].number = number;
            index++;
        }
        else if (strcmp(typeOfShares, "sell") == 0)
        {
            cin >> price >> number;
            shares[index].buyOrSell = true;
            shares[index].price = price;
            shares[index].number = number;
            index++;
        }
        else if (strcmp(typeOfShares, "cancel") == 0)
        {
            int recordth;
            cin >> recordth;
            cancelRecord(recordth);
        }
        else
        {
            computePriceAndMax(index - 1, perPrice, perNumber);
            cout << perPrice << ' ' << perNumber << endl;
        }
        memset(typeOfShares, 0, 10);
    }
}

int min(int num1, int num2)
{
    if (num1 <= num2)
        return num1;
    else
        return num2;
}

//取消的第th条交易股
void cancelRecord(int th)
{
    shares[th].price = 0.00;
    shares[th].number = 0;
    shares[th].enable = false;
}

//从未分类的交易股，按照条件进行分类存储，并进行排序
void divTypeOfShares(int n, int &lenOfSell, int& lenOfBuy)
{
    int i = 1, j = 0, k = 0;
    for (; i <= n; i++)
    {
        if (shares[i].buyOrSell == false && shares[i].enable == true)
            sharesBuy[j++] = shares[i];
        else if (shares[i].buyOrSell == true && shares[i].enable == true)
            sharesSell[k++] = shares[i];
    }

    lenOfBuy = j;
    lenOfSell = k;
    sort(sharesBuy, sharesBuy + lenOfBuy, cmpBuy);
    sort(sharesSell, sharesSell + lenOfSell, cmpSell);
}

void computePriceAndMax(int n, double& perPrice, int& perNumber)
{
    double tmpPrice;//临时存储最优的开盘价
    int sumBuy = 0, sumSell = 0;//买的总股数和卖的总股数
    int lenOfSharesBuy, lenOfSharesSell;//买家类型数组长度，卖家类型数组长度
    divTypeOfShares(n, lenOfSharesSell, lenOfSharesBuy);

    for (int i = 0; i < lenOfSharesBuy; i++)
    {
        /*由前面的买家交易股的排序知道当前的交易股，其价格是大于等于其前面的交易股的。
        那么如果它的股数比前面所有的交易股之和大或者相等，则无需购买前面的交易股。
        */
        if (sharesBuy[i].number > sumBuy)
        {
            tmpPrice = sharesBuy[i].price;
            sumBuy = sharesBuy[i].number;
        }
        else
            sumBuy += sharesBuy[i].number;
        sumSell = 0;
        for (int j = 0; j < lenOfSharesSell; j++)
        {
            //如果当前的卖家股的价格比开盘价高，则不能购买，跳过
            if (sharesSell[j].price > tmpPrice)
                continue;
            sumSell += sharesSell[j].number;
        }

        if (perNumber <= min(sumBuy, sumSell))
        {
            perNumber = min(sumBuy, sumSell);
            perPrice = tmpPrice;
        }

    }
}