题目描述

某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。

该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：

1. buy p s 表示一个购买股票的买单，每手出价为 p，购买股数为 s。
2. sell p s 表示一个出售股票的卖单，每手出价为 p，出售股数为 s。
3. cancel i 表示撤销第 i 行的记录。被撤销的记录一定是前两种。

如果开盘价为p0，则系统可以将所有出价至少为 p0 的买单和所有出价至多为 p0 的卖单进行匹配。

因此，此时的开盘成交量为出价至少为 p0 的买单的总股数和所有出价至多为 p0 的卖单的总股数之间的较小值。

你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。

如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。

输入格式

输入数据有任意多行，每一行是一条记录。

保证输入合法。股数为不超过 108 的正整数，出价为精确到恰好小数点后两位的正实数，且不超过 10000.00。

输出格式

你需要输出一行，包含两个数，以一个空格分隔。

第一个数是开盘价，第二个是此开盘价下的成交量。

开盘价需要精确到小数点后恰好两位。

数据范围

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

$0<p≤10^4$

$1≤s≤10^8$

数据保证一定存在某个开盘价使得成交量不为 0。
保证输入合法。数据保证 cancel 指令只会取消 buy 和 sell 记录。

输入样例：

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

思路

(本人只是一个蒟蒻，所以在这里就直接写暴力枚举的了，想看前缀和+双指针的小伙伴可以看一下y总的代码)

为了方便表示，我们可以定义一个结构体，每次输入的时候，判断输入的是买还是卖，分别进行处理】

如果输入的是撤销，那么就把撤销的句子标记一下（这句话也要标记，因为到后面我们要对没有标记的句子进行处理）

根据题意，我们将大于p0的买股加到一起，再把小于p0的卖股加到一起，取一个最小值

然后再定义一个初值为0的两个数，方便比较

注意1：在最后比较的时候，大于和等于的情况要分开写，因为&&的运算及比||高，结果不一样的

注意2：本题s的数据范围是$1≤s≤10^8$,所以可能爆int，要用long long

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n;
struct record
{
    int type;
    double p;
    int s;
    bool is_del;
}d[5010];
int main()
{
    string type;
    while(cin>>type)
    {
        if(type=="buy")
        {
            double p;
            int s;
            cin>>p>>s;
            d[++n]={1,p,s};
        }
        else if(type=="sell")
        {
            double p;
            int s;
            cin>>p>>s;
            d[++n]={2,p,s};
        }
        else
        {
            int id;
            cin>>id;
            d[id].is_del=1;
            d[++n].is_del=1;
        }
    }
    double resp=0;
    long long  ress=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i].is_del==0)
        {
            double p=d[i].p;
            long long  s1=0,s2=0;
            for(int j=1;j<=n;j++)
            {
                if(d[j].is_del==0)
                {
                    if(d[j].type==1&&d[j].p>=p) s1+=d[j].s;
                    else if(d[j].type==2&&d[j].p<=p) s2+=d[j].s;
                }
            }
            long long  t=min(s1,s2);
            if(t>ress||t==ress&&p>resp)
                resp=p,ress=t;
        }
    }
    printf("%.2lf %lld\n", resp, ress);
    return 0;
}