题目描述
问题分析 :
将问题简化后就是 取订一个price 判断得到最小的售出买入的值 ress = min(s1, s2)
对于买入的price 大于取定的price的s 是可取得值 s1 += s;
对于售出的price 小于取定的price的s 是可取的值 s2 += s;
重点分析 :
对于每个节点用结构体来存储他们的信息
按买入和卖出进行读入
如果输入的是撤销,那么就把撤销的句子标记一下 (这句话本身也要标记,因为到后面我们要对没有标记的句子进行处理 cancel语句本身也是要被删掉的)
注意 :
需要开long long (5000 * 1e8)
样例
blablabla
枚举
(暴力枚举) $O(n^2)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5010;
int n;
struct Node{
int type;
double p;
LL s;
bool is_del;
}w[N];
int main()
{
string type;
while (cin >> type)
{
if (type == "buy")
{
double p;
int s;
cin >> p >> s;
w[++ n] = {1,p,s};
}
else if (type == "sell")
{
double p;
int s;
cin >> p >> s;
w[++ n] = {2,p,s};
}
else
{
int id;
cin >> id;
w[id].is_del = true;
w[++ n].is_del = true;
}
}
double resp;
LL ress = 0;
for (int i = 1; i <= n; i ++)
if (w[i].is_del == false)
{
double p = w[i].p;
LL s1 = 0, s2 = 0;
for (int j = 1; j <= n; j ++)
{
if (w[j].is_del == false)
if (w[j].type == 1 && w[j].p >= p) s1 += w[j].s;
else if (w[j].type == 2 && w[j].p <= p) s2 += w[j].s;
}
LL t = min(s1, s2);
if (t > ress || t == ress && p > resp)
resp = p, ress = t;
}
printf("%.2lf %lld", resp, ress);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla