鄙人不才,此中鄙陋甚多,望海涵!!!
首先 buy
与 sell
肯定不存在什么歧义,存在歧义的只有cancel
,这里我们来详细的解读一下关于cancel
的一些误区!!!
1. 会不会出现后面的cancel取消了前面的cancel,从而导致前面的cancel失效?
答:会出现后面cancel取消前面的cancel,但前面的那一条在它出现的时候就生效了,而不会失效,相当于
撤销了一条已经起完作用的命令
2.会不会出现有cancel取消的是还没有出现命令,比如现在的cancel是第五行,取消的是第6行的命令
答:会,但不会对第6行起到作用,这里你可以理解为cancel只有及时生效的的作用,一单取消的是当前没
有的命令,并不会起到什么实际作用
综上所述这个题目是真的垃圾,什么都没有说,上述这些关于cancel
的误区是我提交了n次之后才发现的一些令人恶心的地方!有了上面的解读,我们只需要按顺序处理命令即可!
算法流程
1.先利用结构体存下来操作(注意下标从1开始)
2.遇到的撤销的就把对应下标的结构体重置为0
3.遍历结构体,区分买与卖的有效信息
4.这里它给出的价格每次都是精确到2位小数的,然而我是想,对于买与卖中存在的至少与至多的关系,我们可以分别用前缀和与后缀和来解决,但前提是价格必须为int型,因此我就先把他们放大了100倍,到后面输出的时候再缩小即可!
5.做完前缀和与后缀和之后再遍历1到100万中的价格,在股数最大的情况下取到最高的价格即可!
6.最后不要忘记是long long类型,否则会爆!
方法点评:网上的代码大都都是利用结构体再排序,或者堆来解决,我这个方法虽然占些内存(其实无关紧要),但思路简单,代码简洁,少处理了许多东西,望大家借鉴!
C++Code
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e6+10,M=5010;
LL f[N],b[N];
LL bu[N],se[N];
struct infor
{
int t,p,c;
}inf[M];
char s[10];
int cnt,res;
float price;
int main()
{
while(~scanf("%s",s))
{
++cnt;
if(*s=='b')
{
scanf("%f%d",&price,&res);
price=price*100;
inf[cnt]={1,(int)price,res};
}
else if(*s=='s')
{
scanf("%f%d",&price,&res);
price=price*100;
inf[cnt]={2,(int)price,res};
}
else
{
int tmp;
scanf("%d",&tmp);
inf[tmp]={0,0,0};
}
}
for(int i=1;i<=cnt;i++)
{
if(inf[i].t==1) bu[inf[i].p]+=inf[i].c;
else if(inf[i].t==2) se[inf[i].p]+=inf[i].c;
}
for(int i=1000000;i>=1;i--) b[i]=bu[i]+b[i+1];
for(int i=1;i<=1000000;i++) f[i]=se[i]+f[i-1];
LL x=0,y=0;
for(int i=1;i<=1000000;i++)
if(x<=min(b[i],f[i]))
{
x=min(b[i],f[i]);
y=i;
}
double yr=(double)y/100;
printf("%.2lf %lld\n",yr,x);
return 0;
}