标签：cur int Energy 100005 n1 Vehicle New sum dis
- 怎样实现自定义排序函数的堆呢？
- 从 C++11 开始，如果使用 lambda 函数自定义 Compare 则需要将其作为构造函数的参数代入，如：
priority_queue<int,vector<int>,decltype(cmp)>q(cmp);
- decltype 说明符可以推断表达式的类型
- 当然本题其实不需要自定义排序函数，因为在调用排序运算符时，决不能读取外部数值可能会改变的数组
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],x[100005],t[100005];
deque<int>q[100005];
priority_queue<pair<int,int> >cur;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
long long sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
sum+=a[i];
q[i].clear();
}
for(int i=1;i<=m;i++)
{
cin>>x[i]>>t[i];
q[t[i]].push_back(x[i]);
}
while(cur.size())
{
cur.pop();
}
for(int i=1;i<=n;i++)
{
q[i].push_back(INT_MAX);
cur.push(make_pair(-q[i].front(),i));
}
for(int i=1;i<=m;i++)
{
int dis=x[i]-x[i-1];
while(cur.size())
{
int n1=cur.top().second;
if(-cur.top().first!=q[n1].front())
{
cur.pop();
continue;
}
if(b[n1]>dis)
{
b[n1]-=dis;
dis=0;
break;
}
else if(b[n1]==dis)
{
b[n1]=0;
dis=0;
cur.pop();
break;
}
else
{
dis-=b[n1];
b[n1]=0;
cur.pop();
}
}
if(dis>0)
{
break;
}
sum=sum+a[t[i]]-b[t[i]];
b[t[i]]=a[t[i]];
q[t[i]].pop_front();
cur.push(make_pair(-q[t[i]].front(),t[i]));
}
cout<<sum<<endl;
}
return 0;
}
标签：cur,
int,
Energy,
100005,
n1,
Vehicle,
New,
sum,
dis
From： https://www.cnblogs.com/watersail/p/18509936