12266 - Stock Prices
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3418
In this problem we deal with the calculation of stock prices. You need to know the following things about stock prices:
The ask price is the lowest price at which someone is willing to sell a share of a stock.
The bid price is the highest price at which someone is willing to buy a share of a stock.
The stock price is the price at which the last deal was established.
Whenever the bid price is greater than or equal to the ask price, a deal is established. A buy order offering the bid price is matched with a sell order demanding the ask price, and shares are exchanged at the rate of the ask price until either the sell order or the buy order (or both) is fulfilled (i.e., the buyer wants no more stocks, or the seller wants to sell no more stocks). You will be given a list of orders (either buy or sell) and you have to calculate, after each order, the current ask price, bid price and stock price.
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
One line with an integer n (1 ≤ n ≤ 1 000): the number of orders.
n lines of the form "order_type x shares at y", whereorder_type is either "buy" or "sell", x (1 ≤ x ≤ 1 000) is the number of shares of a stock someone wishes to buy or to sell, and y (1 ≤ y ≤ 1 000) is the desired price.
Output
Per test case:
n lines, each of the form "ai bi si", where ai, bi and si are the current ask, bid and stock prices, respectively, after the i-th order has been processed and all possible deals have taken place. Whenever a price is not defined, output "-" instead of the price.
Sample in- and output
2 6 buy 10 shares at 100 sell 1 shares at 120 sell 20 shares at 110 buy 30 shares at 110 sell 10 shares at 99 buy 1 shares at 120 6 sell 10 shares at 100 buy 1 shares at 80 buy 20 shares at 90 sell 30 shares at 90 buy 10 shares at 101 sell 1 shares at 80
学英语：
after the i-th order has been processed and all possible deals have taken place.
在第i个股票订单被处理，并且所有可能的交易都发生后。
思路：用优先队列实现，buy的大的在前，sell的小的在前。
完整代码：
/*0.025s*/
#include<bits/stdc++.h>
using namespace std;
char buff[10];
struct Buy
{
int price, num;
bool operator < (const Buy& a) const
{
return price < a.price;
}
} b;
struct Sell
{
int price, num;
bool operator < (const Sell& a) const
{
return price > a.price;
}
} s;
priority_queue<Buy> buyseq;///大的在前
priority_queue<Sell> sellseq;///小的在前
int lastprice, delta;
void update()
{
while (!buyseq.empty() && !sellseq.empty() && buyseq.top().price >= sellseq.top().price)///还可以继续交易
{
b = buyseq.top(), s = sellseq.top();
buyseq.pop(), sellseq.pop();
lastprice = s.price;
delta = min(b.num, s.num);
b.num -= delta, s.num -= delta;
if (b.num > 0) buyseq.push(b);
if (s.num > 0) sellseq.push(s);
}
}
void print()
{
if (sellseq.empty()) printf("- ");
else printf("%d ", sellseq.top().price);
if (buyseq.empty()) printf("- ");
else printf("%d ", buyseq.top().price);
if (lastprice == -1) printf("-\n");
else printf("%d\n", lastprice);
}
int main()
{
int T, n, i, num, price;
scanf("%d", &T);
while (T--)
{
while (!buyseq.empty()) buyseq.pop();
while (!sellseq.empty()) sellseq.pop();
lastprice = -1;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%s %d shares at %d", buff, &num, &price);
if (buff[0] == 'b') buyseq.push((Buy){price, num});
else sellseq.push((Sell){price, num});
update();
print();
}
}
return 0;
}
作者：csdn博客 synapse7
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索stock
， ask
， order
， The
， priority_queue
， priority_queue详解
， priority_queue实例
AT
stock prices、uva打印队列、en12266 1、www.712266.com、en12266，以便于您获取更多的相关知识。