洛谷 CF572B题解
思路
首先，将 SELL 和 BUY 交易数据分别存放在两个桶。
接下来，从小到大遍历。取出最小的 \(s\) 个：从大到小遍历，取出最大的 \(s\) 个。分别存放在 queue 和 stack 中，如果不到 \(s\) 就取完为止。
最后，输出 queue 和 stack 中的所有元素即可。
代码实现:
#include<bits/stdc++.h>
using namespace std;
char c ;
int n , s , q[10005] , p[10005] , t1[100005] , t2[100005] , n1 , n2 ;
stack<int> s1 ;
queue<int> s2 ;
signed main(){
cin >> n >> s ;
for( int i = 1 ; i <= n ; i ++ ){
cin >> c >> p[i] >> q[i] ;
if( c == 'S' ){
t1[p[i]] += q[i] ;
}
else{
t2[p[i]] += q[i] ;
}
}
for( int i = 1 ; i <= 100000 ; i ++ ){
if( t1[i] > 0 && n1 < s ){
s1.push( i ) ;
n1 ++ ;
}
}
for( int i = 100000 ; i >= 1 ; i -- ){
if( t2[i] > 0 && n2 < s ){
s2.push( i ) ;
n2 ++ ;
}
}
while( !s1.empty() ){
cout << "S " << s1.top() << " " << t1[s1.top()] << "\n" ;
s1.pop() ;
}
while( !s2.empty() ){
cout << "B " << s2.front() << " " << t2[s2.front()] << "\n" ;
s2.pop() ;
}
return 0 ;
}