ภารกิจคือการหาจำนวนสูงสุดของ line segments ที่สามารถครอบคลุมจุดที่กำหนดได้
ได้รับอาร์เรย์ a1[] ขนาด n1 และจำนวนเต็ม 2 ตัว A และ B จาก a1[] สร้าง n1 line segments ที่มีจุดเริ่มต้นและจุดสิ้นสุดเป็น a1[i] - A และ a1[i] + B ตามลำดับ
อีกอาร์เรย์ a2[] ขนาด n2 มีจุดที่ต้องมอบหมายให้ line segments โดยที่จำนวน line segments ที่ได้รับมอบหมายจุดต้องมากที่สุด หมายเหตุ: จุดเดียวสามารถมอบหมายให้ line segment ได้เพียงครั้งเดียว
ตัวอย่าง
อินพุต
a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2
เอาต์พุต
1
คำอธิบาย
Line segments ที่สร้างได้จาก a1[i] - A และ a1[i] + B คือ (0, 6) และ (3, 7)
จุดแรกใน a2[] คือ 2 สามารถมอบให้ segment แรก จุดถัดไป 8 ไม่สามารถมอบให้ segment ใดได้ ดังนั้นมีเพียง 1 segment ที่ได้รับจุด
อินพุต
a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1
เอาต์พุต
4
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- เริ่มต้น vectors a1 และ a2 และจำนวนเต็ม A และ B ใน main ด้วยค่าที่กำหนด
- สร้างตัวแปร n1 และ n2 เก็บขนาดของ vectors a1 และ a2
- ใน Max() เรียงลำดับ vectors a1 และ a2 ทั้งคู่
- เริ่มต้น j = 0 และ ans = 0 สำหรับติดตาม a2 และคำตอบ
- ลูป i = 0 ถึง i < n1
- ใน for loop เริ่ม while loop j < n2
- ถ้า a1[i] + B < a2[j] break ออก while loop
- มิฉะนั้น ถ้า a2[j] >= a1[i] - A && a2[j] <= a1[i] + B เพิ่ม ans และ j แล้ว break
- มิฉะนั้น เพิ่ม j
- คืนค่า ans
ตัวอย่างโปรแกรม
#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B) {
// เรียงลำดับ a1 และ a2
sort(a1.begin(), a1.end());
sort(a2.begin(), a2.end());
int j = 0;
int ans = 0;
for (int i = 0; i < n1; i++) {
// ค้นหาจุด
while (j < n2) {
// ถ้าจุดสิ้นสุด segment น้อยกว่าจุดปัจจุบัน
if (a1[i] + B < a2[j])
break;
// จุดอยู่ใน segment
if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B) {
ans++;
j++;
break;
} else
j++;
}
}
return ans;
}
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
