A Retribution!

本文主要是介绍A Retribution!，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题链接
考察:贪心
思路:
  死于读不懂题,对于每个仓库,求裁判到它的距离,排序,两类仓库分开求,因为题目是这么说的

Code

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int N =1010;
typedef pair<double,int> PII;
int n,m,p;
bool vis[N*3];
int xx[N*3],yy[N*3];
struct Node{
	int l,r;
	double d;
	bool operator<(const Node& q)const{
		if(fabs(q.d-this->d)<=1e-6){//优先级大 排前面 
			if(q.l==this->l) return q.r<this->r;
			return q.l<this->l;//true 新的优先级更大 
		}
		return q.d<this->d;
	}
};
double Dist(int x,int y,int a,int b)
{
	return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n+m+p;i++) scanf("%d%d",&xx[i],&yy[i]);
	priority_queue<Node,vector<Node>,less<Node> > q;
	for(int i=1;i<=n;i++)
	  for(int j=n+1;j<=n+m;j++)
	    q.push({i,j,Dist(xx[i],yy[i],xx[j],yy[j])});
	double sum = 0;
	while(q.size())
	{
		Node it = q.top();
		q.pop();
		if(vis[it.l]||vis[it.r]) continue;
		vis[it.l] = vis[it.r] = 1;
		sum+=it.d;
	}
	for(int i=1;i<=n;i++)
	  for(int j=n+m+1;j<=n+m+p;j++)
	    q.push({i,j,Dist(xx[i],yy[i],xx[j],yy[j])});
	memset(vis,0,sizeof vis);
	while(q.size())
	{
		Node it = q.top();
		q.pop();
		if(vis[it.l]||vis[it.r]) continue;
		vis[it.l] = vis[it.r] = 1;
		sum+=it.d;
	}
	printf("%.10lf\n",sum);
	return 0;
}

  关于此想总结下优先队列.
(1) 默认优先队列是\(less<T>\),即重载\(<\)号,此时\(this\)与新对象比较,如果返回\(true\),说明新对象优先级大,排前面.
(2) \(great<T>\)重载大于号

这篇关于A Retribution!的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！