洛谷 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 ;
}