Solution:
对股票出价进行排序,然后按照价格递增的次序依次设定p的价格并求成交量。
1.
//prove that the result of price(maximum--maxprice) is info[k].price:
//If not,the nearest data that is bigger than price
//result=maxresult & price>maxprice , conflict
2.
//po assending as times by
//so if maxamount is the same, use the newest
3.buy
先比较并设置maxamount值
再 买单 减
4.
sell
先 卖单 加
再比较并设置maxamount值
注意
1.出价价格的重复性
2.buy sell出价价格相同
3.数据2^64内的范围,用long long 或__int64。
而c注意用%I64d或%lld。而与购买股数有关的变量全部用long long 或__int64,不要遗漏,如min和max函数要用到long long 或__int64。
当你的程序为80分时,就是第三点没考虑。
建议:
把buy,sell合并或分开都可以,把相同价格的值分开或合并都可以,虽然后者时间效率会高一点,
但是无疑考试期间把把buy,sell合并,不把相同价格的值合并更容易写,更容易理解,也不容易写错。
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 8000 //The softest way to write a right code in a competition
//Just time limite, we don't need to write the best code(in time aspect) struct node
{
double price;
//mode: 1:sell 0:buy
//why put sell ahead of buy?
//sell:add & buy:delete --- we need maximum
long amount,mode;
}info[maxn+]; bool cmp(struct node a,struct node b)
{
if (a.price<b.price)
return true;
else if (a.price>b.price)
return false;
else if (a.mode>b.mode)
return true;
else
return false;
} __int64 min(__int64 a,__int64 b)
{
if (a>b)
return b;
else
return a;
} int main()
{
long g,pos,ans,i,b[maxn+],c[maxn+];
__int64 x,y,z,maxamount;
double a[maxn+],maxprice;
char s[];
bool vis[maxn+];
//use stdlib.h faster!
g=;
while (scanf("%s",s)!=EOF)
{
g++;
if (strcmp(s,"cancel")==)
{
scanf("%ld",&pos);
vis[g]=false;
vis[pos]=false;
}
else
{
//pay attention:%lf double a[]
scanf("%lf%ld",&a[g],&b[g]);
if (strcmp(s,"sell")==)
c[g]=;
else
c[g]=;
vis[g]=true;
}
}
ans=;
for (i=;i<=g;i++)
if (vis[i])
{
info[ans].price=a[i];
info[ans].amount=b[i];
info[ans].mode=c[i];
ans++;
}
sort(info,info+ans,cmp);
//prove that the result of price(maximum--maxprice) is info[k].price:
//If not,the nearest data that is bigger than price
//result=maxresult & price>maxprice , conflict //choose
//in >= po
//out <= po //po assending as times by
//so if maxamount is the same, use the newest //buy
x=;
for (i=;i<ans;i++)
if (info[i].mode==)
x+=info[i].amount;
//sell
y=;
maxamount=;
for (i=;i<ans;i++)
//when po is info[i].price
//buy
if (info[i].mode==)
{
z=min(x,y);
if (z>=maxamount)
{
maxamount=z;
maxprice=info[i].price;
}
x-=info[i].amount;
}
//sell
else
{
y+=info[i].amount;
z=min(x,y);
if (z>=maxamount)
{
maxamount=z;
maxprice=info[i].price;
}
}
//数据默认maxamount>0
printf("%.2lf %I64d",maxprice,maxamount);
return ;
}