在执行 K 个操作的所有可能选择后，给定二进制字符串中设置位数的平均值
在此问题中，我们需要在对给定字符串执行所有选择的 K 个操作后找到设置位数的平均值。
可以使用蛮力方法来解决此问题，但我们将使用概率原理来克服蛮力方法的时间复杂度。
问题陈述– 我们给出了一个整数 N、包含 K 个正整数的数组 arr[] 和一个长度为 N 且仅包含设置位的二进制字符串。我们需要在执行 K 个操作的所有可能选择后找到设置位数的平均值。在第 i 次操作中，我们可以翻转给定字符串的任意 arr[i] 位。
示例
输入– N = 2, arr[] = {1, 2>
输出– 1
解释– 初始二进制字符串为 11。
在第一步中，我们可以翻转第一个字符，字符串将为 01。
在第二次操作中，我们需要翻转任意两位。所以字符串将是 10。
第二个选择可以从第一步翻转第二个字符开始，字符串将是 10。
在当前操作的第二步，我们需要翻转任意 2 位，字符串可以是 01。
所以，我们有 2 个选择，最终字符串可以是 01 或 10。
总选择 = 2，最终字符串中的总设置位 = 2，ans = 2/2 = 1。
输入 – N = 3，arr[] = {2, 2
输出– 1.6667
解释 – 我们有初始字符串为 111。
在第一个操作中，我们可以翻转任意 2 个字符。因此，字符串可以是 001、100、010。
在第二个操作中，我们可以翻转第一个操作得到的结果字符串中的 2 位。
当我们翻转 001 的任意 2 位时，我们得到 111、010 和 100。
当我们翻转 100 的任意 2 位时，我们可以得到 010、111 和 001。
当我们翻转 010 的任意 2 位时，我们可以得到 100、001 和 111。
因此，我们在最后一个操作中总共得到了 9 个不同的字符串。
9 个字符串中的总置位位数 = 15，总操作数 = 9，答案 = 15/9 = 1.6667
方法 1
这里我们将使用概率原理来解决问题。假设执行 i-1 次操作后，置位位的平均值是 p，非置位位的平均值是 q。我们需要计算第 i 次操作中设置位和关闭位的平均值。
因此，p 的更新值可以是 p + 新设置位的平均数量 - 新关闭位的平均数量。
算法
用 N 初始化 P，因为我们最初有 N 个设置位，用 0 初始化 Q，因为我们最初有 0 个设置位。
遍历操作数组。
用 P 和 Q 值初始化 prev_p 和 prev_q。
用 prev_p - prev_p * arr[i] / N + prev_q * arr[i] / N 更新 P 值，这会添加翻转为设置位的平均关闭位并删除翻转为关闭位的平均设置位
更新 Q值。
返回 P 值。
示例
#include <bits/stdc++.h>
using namespace std;
double getAverageBits(int len, int K, int array[]) {
// 将平均"1"存储在二进制字符串中
double P = len;
// 将平均"0"存储在二进制字符串中
double Q = 0;
// 遍历数组 array[]
for (int i = 0; i < K; i++) {
// 使用上一次迭代获得的 P 和 Q 初始化 prev_p 和 prev_q
double prev_p = P, prev_q = Q;
// 更新平均 '1'
P = prev_p - prev_p * array[i] / len + prev_q * array[i] / len;
// 更新平均 '0'
Q = prev_q - prev_q * array[i] / len + prev_p * array[i] / len;
}
return P;
}
int main() {
int N = 2;
int array[] = {1};
int K = sizeof(array) / sizeof(array[0]);
cout << "执行操作后设置位数的平均值为 " << getAverageBits(N, K, array);
return 0;
}
输出
执行操作后设置位的平均数量为 1
时间复杂度 - O(K)，其中 K 是数组的长度。
空间复杂度 - O(1)，因为我们不使用任何额外空间。
在本教程中，我们学习了在执行 K 操作的所有可能选择后找到平均设置位。在单一选择中，我们需要执行数组中给出的所有操作。
