จำนวนเซ็กเมนต์สูงสุดที่สามารถมีจุดที่กำหนดใน C++

ภารกิจคือการค้นหาส่วนสูงสุดที่สามารถมีคะแนนที่กำหนดได้

กำหนดอาร์เรย์ a1[] ที่มีขนาด n1 และกำหนดจำนวนเต็ม A และ B สองจำนวน จากอาร์เรย์ที่กำหนด a1[],n1 ส่วนของเส้นตรงสามารถเกิดขึ้นได้โดยมีจุดเริ่มต้นและจุดสิ้นสุดเป็น a1[i] – A และ a1[i] + ตามลำดับ

อาร์เรย์อื่น a2[] จะได้รับด้วยจำนวนคะแนน n2 จุดเหล่านี้จะต้องถูกกำหนดให้กับส่วนเส้นเพื่อให้จำนวนส่วนของเส้นมากกว่าที่ได้รับมอบหมายจุดสูงสุด โปรดทราบว่าจุดเดียวสามารถกำหนดได้เพียงครั้งเดียวให้กับส่วนของเส้นที่กำหนด

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง:

อินพุต

a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2

ผลลัพธ์

1

คำอธิบาย − ส่วนของเส้นตรงที่เกิดจากจุด a1[i] – A และ a1[i] + B คือ (0, 6) และ (3, 7)

จุดแรกในอาร์เรย์ a2[] นั่นคือ 2 สามารถกำหนดให้กับส่วนของบรรทัดแรกได้ ในขณะที่จุดถัดไป 8 ไม่สามารถกำหนดให้กับส่วนของเส้นตรงได้ ดังนั้น สามารถกำหนดส่วนของเส้นตรงได้เพียง 1 จุด และผลลัพธ์จะกลายเป็น 1

อินพุต

a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1

ผลลัพธ์

4

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• เริ่มต้นเวกเตอร์ a1 และ a2 และจำนวนเต็ม A และ B ในฟังก์ชันหลักด้วยค่าที่แน่นอน

• สร้างตัวแปร n1 และ n2 และเก็บไว้ในนั้น ขนาดของเวกเตอร์ a1 และ a2 ตามลำดับ

• ในฟังก์ชัน Max() ให้เรียงลำดับทั้งเวกเตอร์ a1 และ a2 ก่อน

• เริ่มต้น j =0 และ ans =0 เพื่อติดตามเวกเตอร์ a2 และคำตอบสุดท้ายตามลำดับ

• วนจาก i =0 ถึง i

• ภายใน For loop เริ่มต้นอีกครั้ง while loop โดยมีเงื่อนไข j

• ตรวจสอบว่า (a1[i] + B

• ให้ตรวจสอบว่า (a2[j]>=a1[i] - A &&a2[j] <=a1[i] + B) ถ้าเป็นเช่นนั้น ให้เพิ่ม ans andj และแยกตัวออกจากลูป while

• หากข้อความข้างต้นไม่เป็นความจริง ให้เพิ่ม j

• คืนสินค้า

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){
   //sorting a1 and a2
   sort(a1.begin(), a1.end());
   sort(a2.begin(), a2.end());
   int j = 0;
   int ans = 0;
   for (int i = 0; i < n1; i++){
      // searching for point
      while (j < n2){
         /* If ending point of segment is
         smaller than the current point*/
         if (a1[i] + B < a2[j])
            break;
            //
         if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B){
            ans++;
            j++;
            break;
         }
         else
            j++;
      }
   }
   return ans;
}
// main function
int main(){
   int A = 0, B = 1;
   vector<int> a1 = { 1, 2, 3, 4, 6, 7 };
   int n1 = a1.size();
   vector<int> a2 = { 2, 5, 6, 8 };
   int n2 = a2.size();
   cout << Max(a1, a2, n1, n2, A, B);
   return 0;
}

ผลลัพธ์

4