$\mathcal O(n\log n)$
C++ 代码
#include<bits/stdc++.h>
int n,a;
long long ans;
std::priority_queue<int>q;
int main(){
scanf("%d",&n);
while(n--){
scanf("%d",&a);
q.push(a);
if(a<q.top()){
ans+=q.top()-a;
q.pop();
q.push(a);
}
}
printf("%lld",ans);
}
被卡了@acwing_987
@Abosite
@wkj
只要reverse一下再算一次就可以了详细见
%%%
为什么可以用大根堆做?
个人认为是因为数据有点水,试试9 8 7 6 5就知道
他的大根堆只支持递增