首页 > 其他分享 >CF884D 题解

CF884D 题解

时间:2023-02-05 22:04:10浏览次数:57  
标签:CF884D int 题解 top top3 top2 pop top1

题目传送门

题目分析

开始还真没看出来这题跟 \(\text{P1090}\) 合并果子 的关系。

其实只要逆向思考,把拆分看成效果一样的合并就可以了。而与合并果子不同的是,在这题当中我们可以分成 \(3\) 组,显然这样比分成 \(2\) 组更优。

按照以下思路,不难写出以下代码(其实就是将合并果子的板子改一下):

while(q.size()>=3){
	int top1=q.top();q.pop();int top2=q.top();q.pop();int top3=q.top();q.pop();
	ans+=top1+top2+top3;
	q.push(top1+top2+top3);
}

这样我们就顺利过掉了第一个样例。

接着观察第二个样例,发现当 \(n\) 为偶数时,如果 \(3\) 组分下去,最后一定会剩下 \(2\) 组需要单独合并。那我们不如在开始的时候就将最小的 \(2\) 组进行合并,这样就解决了。

贴上代码

#include<bits/stdc++.h>
#define int long long
#define debug puts("Shiina_Mashiro_kawaii")
#define ok puts("Yes")
#define no puts("No")
using namespace std;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-48;
		c=getchar();
	}
	return x*f;
}
const int maxn=1e5+5;
int n;
int ans;
int a[maxn];
priority_queue<int,vector<int>,greater<int> > q;
inline void init(){
	n=read();
	for(register int i=1;i<=n;++i) q.push(read());
}
signed main(){
	init();
	if(n%2==0){
		int top1=q.top();q.pop();int top2=q.top();q.pop();
		ans+=top1+top2;
		q.push(top1+top2);
	}
	while(q.size()>=3){
		int top1=q.top();q.pop();int top2=q.top();q.pop();int top3=q.top();q.pop();
		ans+=top1+top2+top3;
		q.push(top1+top2+top3);
	}
	printf("%lld",ans);
}

标签:CF884D,int,题解,top,top3,top2,pop,top1
From: https://www.cnblogs.com/yizhixiaoyun/p/17094020.html

相关文章

  • abc285h题解
    考虑容斥,强制要求\(k\)个数为完全平方数,系数为\((-1)^k*C_n^k\)(因为我们要从\(n\)个数选出\(k\)个数作为完全平方数)。则在唯一分解\(p_1^{e_1}...p_n^{e_n}\)中,\(e_1...e_n......
  • "_OBJC_CLASS_$ [文件名1]referenced from in[文件名2]:ld: symbol(s) not found问题
    说实话开发一年多了,遇到了至少三次以上这种问题,很困惑,也很难搞觉得,其实很简单解决办法,在buildPhases中添加文件名1的.m文件即可了。"_OBJC_CLASS_$"PackageTourCustomAnnot......
  • 【题解】20230204解题报告
    解题报告20230204主要学习内容有:动态规划,字符串操作(在另外一篇文章里)T1:P5322[BJOI2019]排兵布阵首先题意是设定有n座城堡,s个玩家(不包括特殊玩家),此时每名玩家都有m......
  • lg9035题解
    考虑枚举\(a_{n-1}=l\),根据题意\(l\leqa_n\leqk+1-l\),这说明\(a_n\)有\(k+1-2l\)种取值。令\(b_i=a_i-a_{i-1}\),则\(b_1\geq1\),\(b_i\geq0(i>1)\),\(b_1+...+b_{n-1}=l......
  • 洛谷P9035 Pont des souvenirs 题解
    题面很简洁,这里不做多说。70pts做法首先考虑到\(a_{n-1}\)和\(a_n\)两项是整个数列\(a\)中的最大的两项,所以若\(a_{n-1}+a_n\)不超过\(k+1\),则数列中任意两项......
  • P2016题解
    P2016题解题目描述Bob要建立一个古城堡,城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能瞭望到所有的路。注意,某个士兵在一个结点上时......
  • CF1666K Kingdom Partition 题解
    神仙网络流题。Description传送门Solution考虑最小割,将每个点\(u\)拆成\(L_u,R_u\)两个点。对于每一条原图中的边\((u,v,w)\),连双向边\((L_u,R_v,w),(L_v,R_u,w)......
  • 题解 ARC155D Avoid Coprime Game
    题解ARC155DAvoidCoprimeGame题意给定一个可重集\(S\),保证\(\gcd_{x\inS}(x)=1\),维护一个初始为\(0\)的整数\(G\),双方轮流操作,每次每人选择\(S\)中一个数......
  • circle 题解(思维+堆)
    题目有\(n\)个圆心在\(x\)轴上的不相交的圆(存在边界重合),求这些圆将平面分为几部分。保证\(1\leqn\leq3\times10^5\),\(-10^9\leqx_i,y_i\leq10^9\)。一个......
  • CF765F Souvenirs 题解
    Preface在会压位Trie的前提下,本题最好想的做法应该是压位Trie+回滚莫队,可是竟然没人写这个做法的题解?Solution我们先转化题意:设\(a_i\)在\([l,r]\)中的前驱后继......