重庆巴南区网站开发公司,网上卖建材的平台,app开发的公司,中国十大品牌网CodeForces - 140C New Year Snowmen
题意#xff1a;
现在来做雪人#xff0c;每个雪人由三个不同大小的雪球构成#xff1a;一个大的#xff0c;一个中等的#xff0c;一个小的。现在有 n 个雪球半径分别为 r1, r2, …, rn. 为了做雪人#xff0c;三个雪球的大小必须…CodeForces - 140C New Year Snowmen
题意
现在来做雪人每个雪人由三个不同大小的雪球构成一个大的一个中等的一个小的。现在有 n 个雪球半径分别为 r1, r2, …, rn. 为了做雪人三个雪球的大小必须两两不同。例如半径分别为 123 的雪球可以做成雪人但 2, 2, 3 或 2, 2, 2 不行。现在需要尽可能做更多雪人。
题解
直接贪心肯定不行比如7,5,2,2,2,1,1,如果贪心上来会选752然后就没有其他答案了。最佳答案应该是尽可能用最多的上面这个例子中2最多尽可能用2然后是1最多然后是5一轮用完后这几个数的数量都要减一然后再找数量最多的三个每次都要找最多的三个因此我们要用到优先队列按照顺序从大到小然后再按半径从大到小每次选顶上三个依次进行即可
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
mapint,intmp;
const int maxn1e59;
struct node{int n;int num;node(int a0,int b0):n(a),num(b){}bool operator (const node a)const{if(a.num!num)return numa.num;else return na.n;}
};
int tmp[4];
int A[maxn],B[maxn],C[maxn];
int main()
{int n;cinn;for(int i1;in;i){int x;cinx;mp[x];}priority_queuenodeq;for(mapint,int::iterator itmp.begin();it!mp.end();it){q.push(node(it-first,it-second));}int sum0;int cnt0;while(q.size()3){node aq.top();q.pop();node bq.top();q.pop();node cq.top();q.pop();sum;tmp[1]a.n;tmp[2]b.n;tmp[3]c.n;sort(tmp1,tmp4);A[cnt]tmp[3];B[cnt]tmp[2];C[cnt]tmp[1];a.num--;b.num--;c.num--;if(a.num0)q.push(node(a.n,a.num));if(b.num0)q.push(node(b.n,b.num));if(c.num0)q.push(node(c.n,c.num)); }coutsumendl;for(int i1;icnt;i){printf(%d %d %d\n,A[i],B[i],C[i]);}return 0;
}
