ภารกิจคือการลบ K อาร์เรย์ย่อยออกจากอาร์เรย์ที่กำหนด Arr[] ที่มีองค์ประกอบบวก N เพื่อให้องค์ประกอบที่เหลือทั้งหมดในอาร์เรย์เป็นจำนวนเฉพาะและขนาดของอาร์เรย์ที่เหลือสูงสุด
ป้อนข้อมูล
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}
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
ขั้นแรกให้เก็บไพรม์ทั้งหมดไว้ในอาร์เรย์ไพรม์อื่น[] โดยใช้ตะแกรงของ Eratosthenes โดยเรียกใช้ฟังก์ชัน sieve()
-
ในฟังก์ชัน MaxSize() เรียกใช้การวนซ้ำจาก i=0 จนถึง i
-
จากนั้นรันลูปอื่นจาก i=1 จนถึง i
-
จากนั้นจัดเรียงเวกเตอร์ diff โดยใช้ฟังก์ชัน sort()
-
ตอนนี้ให้รันลูปอื่นจาก 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
