题意
给定 \(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)\) ,可以通过。