주어진 작업은 배열의 나머지 모든 요소가 소수이고 나머지 배열의 크기가 최대가 되도록 N개의 양수 요소가 있는 지정된 배열 Arr[]에서 정확히 K개의 하위 배열을 삭제하는 것입니다.
입력
Arr[]={4, 3, 3, 4, 3, 4, 3} , K=2 출력
3
설명 − K=2, 이는 2개의 하위 배열만 삭제해야 함을 의미합니다.
삭제된 하위 배열은 Arr[0] 및 Arr[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
-
그런 다음 i=1에서 i
-
그런 다음 sort() 함수를 사용하여 벡터 diff를 정렬합니다.
-
이제 i=1에서 i
-
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