Nhiệm vụ được giao là xóa chính xác K mảng con khỏi một mảng đã cho Arr [] có N phần tử dương sao cho tất cả các phần tử còn lại trong mảng là số nguyên tố và kích thước của mảng còn lại là lớn nhất.
Đầu vào
Arr[]={4, 3, 3, 4, 3, 4, 3} , K=2 Đầu ra
3
Giải thích - K =2, điều này có nghĩa là chỉ phải xóa 2 mảng con.
Các mảng con bị xóa là Arr [0] và Arr [3… 5], mảng Arr [] ={3,3,3} có tất cả các phần tử nguyên tố và kích thước lớn nhất có thể.
Đầu vào
Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2 Đầu ra
3
Giải thích - Các mảng con bị xóa là Arr [1] và Arr [4… 6] và mảng nguyên tố còn lại là Arr [] ={7,2,11}.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Đầu tiên lưu trữ tất cả các số nguyên tố vào một mảng nguyên tố khác [] bằng cách sử dụng sàng của Eratosthenes bằng cách gọi hàm sieve ()
-
Trong hàm MaxSize (), hãy chạy một vòng lặp từ i =0 đến i
-
Sau đó, chạy một vòng lặp khác từ i =1 cho đến i
-
Sau đó, sắp xếp khác biệt vectơ bằng cách sử dụng hàm sort ().
-
Bây giờ, hãy chạy một vòng lặp khác từ i =1 đến i
-
Sử dụng câu lệnh if để kiểm tra trường hợp bất khả thi, đó là khi K =0 và không có vật liệu tổng hợp nào.
-
Nếu K lớn hơn hoặc bằng số hỗn hợp, thì hãy xóa tất cả các tổng hợp bao gồm các số nguyên tố phụ và kích thước của các mảng con này sẽ bị xóa phải là 1, để có được câu trả lời tối ưu
-
Nếu K nhỏ hơn số lượng vật liệu tổng hợp, thì chúng ta sẽ phải xóa những mảng con chứa vật liệu tổng hợp và các mảng con nguyên tố không được thuộc loại này.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
6