首页 > 其他分享 >P8587 新的家乡 题解

P8587 新的家乡 题解

时间:2023-05-25 21:56:15浏览次数:47  
标签:家乡 柱子 int 题解 long P8587 leq mp define

题意

给定 \(n\) 个高度分别为 \(h_i\) 的柱子,两个柱子能合并成一个 \(h_i+h_j\) 的新柱子,每根柱子至多被使用一次。

询问最多能建出多少根高度相同的柱子,并且最优答案下柱子的高度有多少种情况。

\(1\leq n\leq 10^6\) , \(1\leq h_i \leq 3\times 10^3\)。

思路

爆搜!

  • 首先我们想,如果我们 \(n^2\) 正向枚举有多少种方案数,显然会超时。

  • 怎么办呢!我们看到 \(1\leq h_i \leq 3\times 10^3\) ,正难则反!我们直接设 \(f[i]\) 表示柱子高度为 \(i\) 时能有多少根不就行了吗,给一个 \(mp[i]\) 数组存储高度为 \(i\) 的柱子有多少根,然后直接 $ O(h^2) $ 枚举就能过了。

  • 最后给方案数排序,输出最大的有多少根柱子,再看有多少种高度跟他一样就行了。

代码实现

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 3e4 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}

int n,ans;
int mp[N],f[N<<1];
int Max=-1,Min=1e9;/*这些柱子的最小和最大高度*/

il int read()
{
	int f=0,s=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
	for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
	return f ? -s : s;
}

il bool mysort(int a,int b) { return a > b; }

signed main()
{
	n=read();
	for(re int i=1;i<=n;i++) 
	{
		int x = read();mp[x]++;/*存高度,更新最大高度最小高度*/
		Max=max(x,Max),Min=min(x,Min);
	}
	for(re int i=Min*2;i<=Max*2;i++)/*合并后最小的高度肯定就是高度最小的柱子乘以2,最大的高度亦然*/
	{
		for(re int j=1;j<=Max*2;j++)
		{
			if(j*2 > i) break;/*前面一半已经计算了后面的一半了,所以直接break*/
			if(i-j == j) f[i] += mp[j]/2;/*两个相等的柱子相加,那么根数加上总共的一半*/
			else f[i] += min(mp[j],mp[i-j]);/*两个柱子高度不相同,那么就能配凑出两个柱子数量较小的那一个*/
		}
	}
	sort(f+1,f+Max*2+1,mysort);/*从大到小排序*/
	printf("%d ",f[1]);/*输出最多根数*/
	int Maxx = f[1];
	for(int i=1;i<=Max*2+1;i++)
	{
		if(f[i] == Maxx) ans++;/*判断有多少数量相等*/
		else break;
	}
	printf("%d",ans);/*输出高度不同的方案数*/
}
}


时间复杂度 \(O(h^2)\) ,可以通过。

标签:家乡,柱子,int,题解,long,P8587,leq,mp,define
From: https://www.cnblogs.com/bloodstalk/p/17433078.html

相关文章

  • P8585 球状精灵的传说 题解
    很好的一个题题意给你\(n\)个三元组\((r_1,r_2,r_3)\),并定义\(ρ=\lfloor\frac{1}{4}min(r_1,r_2,r_3)^3\rfloor\)。两个三元组能合并当且仅当这两个三元组有至少两个值相同,即从\((x_1,y,z)\)和\((x_2,y,z)\)变为\((x_1+x_2,y,z)\)。\((x,y,z)\)的位置不固定......
  • Android 修改 android/hardware/interfaces 下HIDL接口编译报异常问题解决
    最近要增加hostapd的一个HIDL接口,修改android/hardware/interfaces/wifi/hostapd/1.2/IHostapd.hal文件后编译报错如下:ERROR:[email protected]::IHostapdhashashacaed0a159a521bd4964e0fb8117320849109d3eeaff6a08b4d2506156ce6987whichdoesnotmatch......
  • P2480 古代猪文 题解
    题意:求\[g^{\sum_{k\midn}{n\choosek}}\]对\(999911659\)取模。\(1\len,g\le10^9\)。思路:首先根据欧拉定理,题目转化为求\(\displaystyle\sum_{k\midn}{n\choosek}\)对\(999911658\)取模的值。模数为合数不是很好做,因式分解发现\(999911658=2\times3\times467......
  • JOISC 2021 题解
    JOISC21フードコート(FoodCourt)首先我们发现我们这个删除实际上可以假删除,我们每次问询时求出这个队列目前被删了几个(维护区间加,区间\(\max(0,A-x)\))就可以把删除操作给弄掉了。然后我们考虑对商店做扫描线!因为我们现在其实就是对商店的单点问询,我们这个加入操作也可以在左......
  • 【题解】Codeforces Round 737 (CF1557)
    VP情况:solve:4/5rank:431st评价:VP了一下,我这个shaberB直接5发罚时,耽误了二十多分钟,以及被D各种细节差点搞死。A.EzzatandTwoSubsequences(*800)题目描述:给定一个序列,将其分为\(2\)个组,要求这两个组的平均值之和最大,组内的数不要求在原序列中连续。题目分析:我们......
  • 【题解】CF1062E Company
    传送门先考虑如何求解区间LCA假设要我们求\(8\sim11\)的LCA。那么显然它们的LCA等效于8和11的LCA。发现8和11刚好是“最左”和“最右”的两个顶点,感性理解一下,就可以得出一个结论:区间LCA和dfs序最小的和最大的的LCA是等效的。(这个结论应该还......
  • 题解(教主的魔法)P2801
    题目教主的魔法题目描述教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是$N$个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为$1,2,\ldots,N$。每个人的身高一开始都是不超过$1000$的正整数。教主的魔法每次可以把闭区......
  • 常见问题解决 --- 安卓中一个类中的匿名类和另一个类中的匿名类无法相互传值
      runOnUiThread(newRunnable(){@Overridepublicvoidrun(){//在UI线程中执行的主代码textView.setText("Hello,world!");}});将上面更新主ui放置在匿名内部类的回调方法里即可传值给属性。......
  • AtCoder Beginner Contest 302 H. Ball Collector 题解
    AtCoderBeginnerContest302H.BallCollector题意跳过。可以视作将\(a_i,b_i\)之间连了一条边,然后\(a_i,b_i\)之间只能选一个等价于对于一条边只能选择其一个端点。那么对于只包含树的联通块而言,如果都选择儿子节点,那么会有一个根节点无法被选择上;而对于包含至少一个......
  • NOIP2014普及组试题题解
    1.珠心算测验代码:#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=2e4+39+7;intmp[N],n,a[N],ans=0;intmain(){ cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=1;i<=n;i++){ for(intj=1;j<=n;j++)......