leetcode (重排数组使得)连续子数组的权值和最小

• 题目描述：请重新排列某个仅包含2和3的数组，使得数组的所有连续子数组权值之和最小
• 数组的权值定义为,数组中所有元素之积的因子个数，例如：rank([2,3])=4

$$\begin{gathered} x=p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\cdot \cdot \cdot \times p_k^{c_k} \\ rank=(c_1+1)\times (c_2+1)\times (c_3+1)\cdot \cdot \cdot \times (c_2+1) \end{gathered}$$

• 本题 P1=2 ，P2 =3，2和3互质，所以子数组的权值为（2的个数+1）*（3的个数+1）

$$\begin{gathered} 2n+1个数字，n+1个2，n个3，长度为2n的连续子数组的权值 \\ 顺序的情况: \\ (n+1+1)\ast (n-1+1)+(n+1+1)\ast (n-1+1) \\ =(n+2)\ast (n)+(n+2)\ast (n) \\ 乱序为: \\ (n+1)\ast (n+1)+(n+1)\ast (n+1) \end{gathered}$$
例如：[2,2,2,3,3]和[2,2,3,3,2]的长度为4的连续子数组

• 所以在和的个数相同的情况下，越分散乘积就越大，越集中乘积就越小，排列应为顺序的情况

$$\begin{gathered} 对于某个权值为K的数组，将2换成3的权值为 \\ K\ast \frac{(N_2-1)+1}{N_2+1}\ast \frac{(N_3+1)+1}{N_3+1} \end{gathered}$$

例如：[2,2,2],K=(3+1) * (0+1)=4,
           [2,2,3]K= (2+1) * (1+1)=6 = 4*$\frac{3}{4}$*$\frac{2}{1}$

CG

• 参考： 权值不超过K的连续子数组的数量
• 本题的解答，右边界从0到n,对于每个右边界，左边界从0开始，如果窗口中的因子数量满足条件(大于或等于K)，则收缩左边界直到不满足条件，这样可以得出有几个满足条件的连续子数组。
• 注：在每次重新计算时，作者并没有将j，即左窗口放回到0，因为有边界扩大，之前的j个窗口满足条件，再窗口中加入数值只能增加权值
• 注：作者使用了匿名函数来计算当前窗口的权值： lambda 表达式——匿名函数 auto i= [ ] () { };， 填入 & 时，代表通过引用传递捕捉父作用域的变量 https://blog.csdn.net/lievech/article/details/121393346

#include <stdio.h>
#include<unordered_map>
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
int main() {int n, k;cout<<"N长度的vector有多少连续子数组的权值不小于K"<<endl;cin >> n >> k;vector<int> a(n);unordered_map<int, int> mp;ll cnt = 1, res = 0;//因子数量（cnt）auto addv = [&](int x, int t) {for (int i = 2; i * i <= x; i++) {while (x % i == 0) {cout<<i<<" "<<mp[i]<<endl;cnt /= (mp[i] + 1);cout<<"cnt"<<"<-->"<<cnt<<endl;mp[i] += t;cnt *= (mp[i] + 1);cout<<"cnt"<<"<-->"<<cnt<<endl;x /= i;}}if (x > 1) {cnt /= (mp[x] + 1);cout<<"cnt"<<"-->"<<cnt<<endl;mp[x] += t;cnt *= (mp[x] + 1);}};for (int i = 0, j = 0; i < n; i++) {cin >> a[i];addv(a[i], 1);while (j <= i && cnt >= k) {addv(a[j], -1);j++;}res += j;}cout<<"----->";cout << res << "\n";
}

N长度的vector有多少连续子数组的权值不小于K
3
4
6
2 0
cnt<-->1
cnt<-->2
cnt-->2
2 1
cnt<-->2
cnt<-->2
cnt-->1

N长度的vector有多少连续子数组的权值不小于K
3
4
9
3 0
cnt<-->1
cnt<-->2
3 1
cnt<-->1
cnt<-->3
6
2 0
cnt<-->3
cnt<-->6
cnt-->2
3 3
cnt<-->2
cnt<-->6
3 2
cnt<-->2
cnt<-->4
2 1
cnt<-->2
cnt<-->2
cnt-->1
2 
cnt-->1
----->4