题目描述
写个题解, 以便以后复习
小红希望你构造一个数组,满足以下三个条件:
1. 数组的元素都是素数。
2. 数组所有元素相乘恰好等于x。
3. 数组任意相邻两个元素不等。
题解-
题目考察:分解质因数和如何解决元素相邻之间不相等问题
难点: 如何解决元素相邻之间不相等的问题
这里有个结论就是: 若一个数组中出现最多的次数减一大于总数除(这个数之外的数) 则一定无解,否则,有解
这里采用堆的贪心做法, 解法就是先预处理每个数以及每个数出现的次数
将其一Pair[HTML_REMOVED](count, number)的形式加入到堆中
循环执行
1.若堆中有两个数 a, b,则弹出两个数,按照先后弹出的顺序进行输出a.number, b.number,
在做 a.count–, b.count–. 若大于零依旧将其加入。
2. 若堆中只有一个数, 将其弹出输出即可, 此时直接结束循环。
算法正确的简单证明, 若堆中数目大于等于2,
auto p1 = heap.top(), heap.pop();
auto p2 = heap.top(), heap.pop();
p1.number显然与p2.number不一样, 】
1.现在需要证明做法1是正确的
采用反证法: 若前面输出的数也是p1.number,。
首先肯定的是前面肯定是输出了两个数, 假设PII是 w, a
则w.count >= a.count w.count– a.count– , 则 w.count >= a.count,
显然本次开头依然会输出w而不是a,
(1). w.count > a.count很显然。
(2)需证明 w.count = a.count, 说明 w.number > a.count. 由于采用的是双关键字排序, 所以先弹出来的依然是w。则所以与假设产生矛盾, 故做法1是正确的。
2.现在证明做法2 是正确的
若堆中只有一个数 PII a, 若前面输出的最后一个数也是PII a.
前面输出的倒数第二个数的个数PII b一定是1,而a就有两个了,所以一定不可能。
代码
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define int long long
#define fi first
#define se second
unordered_map<int, int> mp;
priority_queue<PII, vector<PII>> q;
int tag = 0;
void solve(int x)
{
if (x == 1) tag = 1;
int sum = 0, maxv = 0;
for (int i = 2; i <= x / i; i++)
{
while (x % i == 0)
{
x /= i, mp[i]++;
sum++, maxv = max(maxv, mp[i]);
};
}
if (x > 1) sum++, mp[x]++, maxv = max(maxv, mp[x]);
if (maxv - 1 > sum - maxv) tag = 1;
for (auto p:mp) q.push({p.se, p.fi});
if (tag) cout << -1;
else cout << sum << "\n";
while (q.size() && !tag)
{
if (q.size() >= 2)
{
auto p1 = q.top(); q.pop();
auto p2 = q.top(); q.pop();
p1.fi--, p2.fi--;
cout << p1.se << " " << p2.se << " ";
if (p1.fi) q.push({p1.fi, p1.se});
if (p2.fi) q.push({p2.fi, p2.se});
continue;
}
cout << q.top().se;
return ;
}
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = 1;
int x;
cin >> x;
while (T--)
{
solve(x);
}
return 0;
}