JZTXT

洛谷 CF572B题解

发布时间 2023-08-08 10:41:39作者: SSSSSSSSSSoil

原题

这是一道洛谷 RMJ 题目。

CF链接

洛谷链接

### 思路

首先，将 SELL 和 BUY 交易数据分别存放在两个桶。

接下来，从小到大遍历。取出最小的 \(s\) 个：从大到小遍历，取出最大的 \(s\) 个。分别存放在 queue 和 stack 中，如果不到 \(s\) 就取完为止。

最后，输出 queue 和 stack 中的所有元素即可。

### 代码实现:

cpp<br />#include&lt;bits/stdc++.h&gt;<br />using namespace std;<br />char c ;<br />int n , s , q[10005] , p[10005] , t1[100005] , t2[100005] , n1 , n2 ;<br />stack&lt;int&gt; s1 ;<br />queue&lt;int&gt; s2 ;<br />signed main(){<br />&nbsp;&nbsp; &nbsp;cin &gt;&gt; n &gt;&gt; s ;<br />&nbsp;&nbsp; &nbsp;for( int i = 1 ; i &lt;= n ; i ++ ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;cin &gt;&gt; c &gt;&gt; p[i] &gt;&gt; q[i] ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if( c == 'S' ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t1[p[i]] += q[i] ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;else{<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t2[p[i]] += q[i] ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;for( int i = 1 ; i &lt;= 100000 ; i ++ ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if( t1[i] &gt; 0 &amp;&amp; n1 &lt; s ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;s1.push( i ) ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;n1 ++ ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;for( int i = 100000 ; i &gt;= 1 ; i -- ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if( t2[i] &gt; 0 &amp;&amp; n2 &lt; s ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;s2.push( i ) ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;n2 ++ ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;while( !s1.empty() ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;cout &lt;&lt; "S " &lt;&lt; s1.top() &lt;&lt; " " &lt;&lt; t1[s1.top()] &lt;&lt; "\n" ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;s1.pop() ;<br />&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;while( !s2.empty() ){<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;cout &lt;&lt; "B " &lt;&lt; s2.front() &lt;&lt; " " &lt;&lt; t2[s2.front()] &lt;&lt; "\n" ;<br />&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;s2.pop() ;<br />&nbsp;&nbsp; &nbsp;}<br />&nbsp;&nbsp; &nbsp;return 0 ;<br />}<br />