数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在C++中通过删除恰好k个子数组来最大化数组大小，使其成为素数数组
给定任务是从具有N个正元素的给定数组Arr[]中删除恰好K个子数组，使得数组中所有剩余元素都是素数，并且剩余数组的大小最大。
输入
Arr[]={4, 3, 3, 4, 3, 4, 3} , K=2输出
3
解释 − K=2，这意味着必须删除2个子数组。
删除的子数组是Arr[0]和Arr[3…5]，留下数组Arr[]={3,3,3}，其中所有元素都是素数，并且大小最大。
输入
Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2输出
3
解释 − 删除的子数组是Arr[1]和Arr[4…6]，剩下的素数数组是Arr[]={7,2,11}。
下面程序中使用的算法如下
首先，使用埃拉托斯特尼筛法（通过调用sieve()函数）将所有素数存储到另一个数组prime[]中。
在MaxSize()函数中，从i=0循环到i<N，并将所有合数的索引号存储到int类型的向量vect中。
然后，从i=1循环到i<vect.size，计算两个连续合数之间素数的数量，并将结果存储到int类型的向量diff中。
然后，使用sort()函数对向量diff进行排序。
现在，从i=1循环到i<diff.size()，计算该向量的累加和，这将帮助我们知道需要删除多少个素数。
使用if语句检查不可能的情况，即当K=0且没有合数时。
如果K大于或等于合数的数量，则删除所有合数，包括多余的素数，并且这些要删除的子数组的大小应为1，以获得最佳答案。
如果K小于合数的数量，则必须删除包含合数的子数组，而素数子数组不应该属于此类别。
示例
#include <bits/stdc++.h>
using namespace std;
const int Num = 1e5;
bool prime[Num];
//Sieve of Eratosthenes
void sieve(){
for (int i = 2; i < Num; i++) {
if (!prime[i]){
for (int j = i + i; j < Num; j += i){
prime[j] = 1;
}
}
}
prime[1] = 1;
}
int MaxSize(int* arr, int N, int K){
vector<int> vect, diff;
//Inserting the indices of composite numbers
for (int i = 0; i < N; i++){
if (prime[arr[i]])
vect.push_back(i);
}
/*Computing the number of prime numbers between
two consecutive composite numbers*/
for (int i = 1; i < vect.size(); i++){
diff.push_back(vect[i] - vect[i - 1] - 1);
}
//Sorting the diff vector
sort(diff.begin(), diff.end());
//Computing the prefix sum of diff vector
for (int i = 1; i < diff.size(); i++){
diff[i] += diff[i - 1];
}
//Impossible case
if (K > N || (K == 0 && vect.size())){
return -1;
}
//Deleting sub-arrays of length 1
else if (vect.size() <= K){
return (N - K);
}
/*Finding the number of primes to be deleted
when deleting the sub-arrays*/
else if (vect.size() > K){
int tt = vect.size() - K;
int sum = 0;
sum += diff[tt - 1];
int res = N - (vect.size() + sum);
return res;
}
}
//Main function
int main(){
sieve();
int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<< MaxSize(arr, N, K);
return 0;
}输出
如果运行上述代码，将得到以下输出：
6
更新于：2020年8月17日
90 次浏览
广告