题解 | 小柒的行列改写

既然是贪心和优先队列，怎么能没有优先队列的题解呢；

简单解释一下逻辑，

将r和c放入pqr和pqc两个优先队列，

比较哪个更小就优先使用，

每次使用行会覆盖先前使用的列的元素和，每次使用列会覆盖先前使用行的总和，

那么只需要开一个gc和gr来统计被覆盖行列总和就行了，

sum就先加上对用行列带来的数值改变再减去被覆盖的值就行了

（还要防止pq为空就可以ac了）

#include <bits/stdc++.h>
using namespace std;
#define int long long
priority_queue<int,vector<int>,greater<int>> pqr,pqc;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

signed main() {
	int n,m;
	cin>>n>>m;
	int sum=0;
	int gr=0,gc=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		pqr.push(x);
	}
		for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		pqc.push(x);
	}
	for(int i=1;i<=n+m;i++)
	{
		int x;
		if(pqc.empty())
		{
				x=pqr.top();
			sum+=m*x;
			sum-=gc;
			gr+=x;
			pqr.pop();
			continue;
		}
		if(pqr.empty())
		{
				x=pqc.top();
			sum+=n*x;
			sum-=gr;
			gc+=x;
			pqc.pop();
			continue;
		}
		if(pqr.top()<=pqc.top())
		{
			x=pqr.top();
			sum+=m*x;
			sum-=gc;
			gr+=x;
			pqr.pop();
		}else
		{
				x=pqc.top();
			sum+=n*x;
			sum-=gr;
			gc+=x;
			pqc.pop();
		}
	}
	cout<<sum<<endl;
	return 0;
}