今天每日一题有点东西，一开始直接用vector加插入排序维护两个初始有序的序列但是超时了，应该是维护有序数列的过程中的插入删除操作把时间复杂度顶到n方，1e5的数据范围爆时间就是合理的了，然后考虑用优先队列。优先队列用的是大根堆小根堆，时间复杂度在nlogn左右，然后才过了，还是有一点难度的。
class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
priority_queue<pair<int,int>> buy;//buy存采购，降序
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> sell;//sell存销售，升序
int n=orders.size(),ans=0,mod=1e9+7;
for (int i=0;i<n;i++){
if (orders[i][2]==0){
while(orders[i][1] && !sell.empty() && sell.top().first<=orders[i][0]){//卖出队列最低者
auto [price,amoumt]=sell.top();
sell.pop();
if (amoumt<=orders[i][1]){
ans=(ans-amoumt+mod)%mod;
orders[i][1]-=amoumt;
}else{
sell.push({price,amoumt-orders[i][1]});
ans=(ans-orders[i][1]+mod)%mod;
orders[i][1]=0;
}
}
if (orders[i][1]){
buy.push({orders[i][0],orders[i][1]});//记得加大括号，是同一元素
ans=(ans+orders[i][1])%mod;
}
}else{
while(orders[i][1] && !buy.empty() && buy.top().first>=orders[i][0]){//买入队列最高者
auto [price,amoumt]=buy.top();
buy.pop();
if (amoumt<=orders[i][1]){
ans=(ans-amoumt+mod)%mod;
orders[i][1]-=amoumt;
}else{
buy.push({price,amoumt-orders[i][1]});
ans=(ans-orders[i][1]+mod)%mod;
orders[i][1]=0;
}
}
if (orders[i][1]){
sell.push({orders[i][0],orders[i][1]});
ans=(ans+orders[i][1])%mod;
}
}
}
return ans;
}
};
/*
for (int i=0;i<n;i++){
if (orders[i][2]==0){
for (int j=0;j<sell.size();j++)
if (sell[j][0]<=orders[i][0]){
if (sell[j][1]<=orders[i][1]){
orders[i][1]=orders[i][1]-sell[j][1];
sell.erase(sell.begin()+j);
j--;
}else{
sell[j][1]=sell[j][1]-orders[i][1];
orders[i][1]=0;
break;
}
}
}else{
for (int j=0;j<buy.size();j++)
if (buy[j][0]>=orders[i][0]){
if (buy[j][1]<=orders[i][1]){
orders[i][1]=orders[i][1]-buy[j][1];
buy.erase(buy.begin()+j);
j--;
}else{
buy[j][1]=buy[j][1]-orders[i][1];
orders[i][1]=0;
break;
}
}
}
if (orders[i][1]!=0){
if (orders[i][2]==0){
bool increasebuy=0;
for (int j=0;j<buy.size();j++)
if (buy[j][0]<=orders[i][0]){
buy.insert(buy.begin()+j,orders[i]);
increasebuy=1;
break;
}
if (!increasebuy) buy.insert(buy.end(),orders[i]);
}else{
bool increasesell=0;
for (int j=0;j<sell.size();j++)
if (sell[j][0]>=orders[i][0]){
sell.insert(sell.begin()+j,orders[i]);
increasesell=1;
break;
}
if (!increasesell) sell.insert(sell.end(),orders[i]);
}
}
}
int ans=0;
for (int j=0;j<sell.size();j++)
ans=(ans+sell[j][1]) % 1000000007;
for (int j=0;j<buy.size();j++)
ans=(ans+buy[j][1]) % 1000000007;
return ans;
*/