2.5.22

2.5.22 #

解答 #

建立最小堆和最大堆，最小堆保存卖家的报价，最大堆保存买家的报价。

如果最小堆中的最低卖出价低于最大堆的最高买入价，交易达成，交易份额较大的一方需要重新回到堆内。

测试结果：

代码 #

// 输入格式： buy 20.05 100
var buyer = new MaxPq<Ticket>();
var seller = new MinPq<Ticket>();

var n = int.Parse(Console.ReadLine());
for (var i = 0; i < n; i++)
{
    var ticket = new Ticket();
    var item = Console.ReadLine().Split(' ');

    ticket.Price = double.Parse(item[1]);
    ticket.Share = int.Parse(item[2]);
    if (item[0] == "buy")
        buyer.Insert(ticket);
    else
        seller.Insert(ticket);
}

while (!buyer.IsEmpty() && !seller.IsEmpty())
{
    if (buyer.Max().Price < seller.Min().Price)
        break;
    var buy = buyer.DelMax();
    var sell = seller.DelMin();
    Console.Write("sell $" + sell.Price + " * " + sell.Share);
    if (buy.Share > sell.Share)
    {
        Console.WriteLine(" -> " + sell.Share + " -> $" + buy.Price + " * " + buy.Share + " buy");
        buy.Share -= sell.Share;
        buyer.Insert(buy);

    }
    else if (buy.Share < sell.Share)
    {
        sell.Share -= buy.Share;
        seller.Insert(sell);
        Console.WriteLine(" -> " + buy.Share + " -> $" + buy.Price + " * " + buy.Share + " buy");
    }
    else
    {
        Console.WriteLine(" -> " + sell.Share + " -> $" + buy.Price + " * " + buy.Share + " buy");
    }

}

internal class Ticket : IComparable<Ticket>
{
    public double Price;
    public int Share;

    public int CompareTo(Ticket other)
    {
        return Price.CompareTo(other.Price);
    }
}

另请参阅 #

SortApplication 库