首页 > 代码库 > 【USACO 2008 Mar Gold】 3.Pearl Pairing 贪心 pq
【USACO 2008 Mar Gold】 3.Pearl Pairing 贪心 pq
题意:有若干个颜色,每个颜色有若干头牛。
现在将牛进行配对,使得每对颜色都不一样,有SPJ。
题解:一旦某种颜色的牛数量占当前未配对牛总数最多,那么就要群起而攻之!
利用pq或者heap解决。
代码:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 101000 #define inf 0x3f3f3f3f using namespace std; int n,m; struct KSD { int id,x; bool operator < (const KSD &a)const{return x<a.x;} KSD(int _id=0,int _x=0):id(_id),x(_x){} }A,B; priority_queue<KSD>pq; int main() { // freopen("test.in","r",stdin); int i,j; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d",&j); pq.push(KSD(i,j)); } n>>=1; for(i=1;i<=n;i++) { A=pq.top(),pq.pop(); B=pq.top(),pq.pop(); printf("%d %d\n",A.id,B.id); if(--A.x)pq.push(A); if(--B.x)pq.push(B); } }
【USACO 2008 Mar Gold】 3.Pearl Pairing 贪心 pq
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。