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

news/2024/11/29 23:53:51/

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

$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)$

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

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

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

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

例如：[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