【习题 5-14 UVA

鸦鸦

#include <bits/stdc++.h>　　using namespace std;
　　const int N = 1e4;
　　struct abc {
　　int num, price;
　　abc(int x = 0, int y = 0) :num(x), price(y) {}
　　};
　　abc re[N + 10];
　　struct setcmp1
　　{
　　bool operator () (const int &a, const int &b)
　　{
　　if (re[a].price == re.price)
　　return a < b;
　　else
　　return re[a].price > re.price;
　　}
　　};
　　struct setcmp2
　　{
　　bool operator () (const int &a, const int &b)
　　{
　　if (re[a].price == re.price)
　　return a < b;
　　else
　　return re[a].price < re.price;
　　}
　　};
　　set <int, setcmp1> buyset;//买的价格,越大越好
　　set <int, setcmp2> sellset;//卖的价格,越小越好
　　bool dele[N + 10];//用来记录某个交易是否被删除了。并不用时刻输出集合大小。所以只要遇到了把它删掉就Ok
　　int n;
　　void cl()
　　{
　　bool shan1, shan2;
　　do
　　{
　　shan1 = shan2 = false;
　　while (buyset.size() > 1 && dele[*buyset.begin()]) buyset.erase(buyset.begin()), shan1 = true;
　　while (sellset.size() > 1 && dele[*sellset.begin()]) sellset.erase(sellset.begin()), shan2 = true;
　　} while (shan1 || shan2);
　　}
　　void out()
　　{
　　int num1 = 0, num2 = 0;
　　int price1 = re[*buyset.begin()].price, price2 = re[*sellset.begin()].price;
　　for (auto it : buyset)
　　if (re[it].price == price1)
　　{
　　if (!dele[it]) num1 += re[it].num;
　　}
　　else break;
　　for (auto it : sellset)
　　if (re[it].price == price2)
　　{
　　if (!dele[it]) num2 += re[it].num;
　　}
　　else break;
　　printf(&quot;QUOTE %d %d - %d %d\n&quot;, num1, price1, num2, price2);
　　}
　　int main()
　　{
　　//freopen(&quot;F:\\rush.txt&quot;, &quot;r&quot;, stdin);
　　int kk = 0;
　　while (~scanf(&quot;%d&quot;, &n))
　　{
　　if (kk > 0) puts(&quot;&quot;);
　　kk++;
　　re[N + 1].num = 0, re[N + 1].price = 0;
　　re[N + 2].num = 0, re[N + 2].price = 99999;

　　memset(dele, 0,>　　buyset.clear(); sellset.clear();
　　buyset.insert(N + 1); sellset.insert(N + 2);
　　for (int i = 1; i <= n; i++)
　　{
　　char s[10];
　　scanf(&quot;%s&quot;, s);
　　switch (s[0])
　　{
　　case ('C'):
　　{
　　int x;
　　scanf(&quot;%d&quot;, &x);
　　dele[x] = true;
　　cl();//看看队首是不是要删掉
　　out();
　　break;
　　}
　　case ('B'):
　　{//买进
　　int num, price;
　　scanf(&quot;%d%d&quot;, &num, &price);
　　while (sellset.size() > 1 && num >0 && price >= re[*sellset.begin()].price)
　　{
　　int temp = min(re[*sellset.begin()].num, num), temp2 = re[*sellset.begin()].price;
　　num -= temp;
　　re[*sellset.begin()].num -= temp;
　　if (re[*sellset.begin()].num == 0)
　　{
　　sellset.erase(sellset.begin());
　　cl();
　　}
　　printf(&quot;TRADE %d %d\n&quot;, temp, temp2);
　　}
　　re = abc(num, price);
　　if (num != 0) buyset.insert(i);
　　out();
　　break;
　　}
　　case 'S':
　　{
　　//卖
　　int num, price;
　　scanf(&quot;%d%d&quot;, &num, &price);
　　while (buyset.size() > 1 && num >0 && price <= re[*buyset.begin()].price)
　　{
　　int temp = min(re[*buyset.begin()].num, num), temp2 = re[*buyset.begin()].price;
　　num -= temp;
　　re[*buyset.begin()].num -= temp;
　　if (re[*buyset.begin()].num == 0)
　　{
　　buyset.erase(buyset.begin());
　　cl();
　　}
　　printf(&quot;TRADE %d %d\n&quot;, temp, temp2);
　　}
　　re = abc(num, price);
　　if (num != 0) sellset.insert(i);
　　out();
　　break;
　　}
　　default:
　　break;
　　}
　　}
　　}
　　return 0;
　　}