ধরুন আমাদের একটি তালিকা দেওয়া হয়েছে যাতে বেশ কয়েকটি পূর্ণসংখ্যা রয়েছে। আমাদের অ্যারের প্রতিটি জোড়া মানের মধ্যে পার্থক্য খুঁজে বের করতে হবে এবং k-th ক্ষুদ্রতম পার্থক্য সংখ্যাটি বের করতে হবে। সূচকটি 0 থেকে শুরু হয় এবং k মানটি আমাদের ইনপুট হিসাবে দেওয়া হয়।
সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় ={2, 6, 4, 8}, k =2, তাহলে আউটপুট হবে 2।
জোড়ার মধ্যে পার্থক্য হল −
(2, 6) =4
(2, 4) =2
(2, 8) =6
(6, 4) =2
(6, 8) =2
(4, 8) =4
যদি আমরা মানগুলি সাজাই, তাহলে এটি 2, 2, 2, 4, 4, 6 হয়ে যায়। 2-য় ক্ষুদ্রতম মান হল 2। (সূচী 0 থেকে শুরু হয়)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- k 1 দ্বারা বাড়ান
- অ্যারে ইনপুট সাজান
- le :=0
- ri :=ইনপুটের শেষ উপাদান - ইনপুটের প্রথম আইটেম
- যখন le
- মধ্য :=(লে + রি) / 2
- tmp :=0
- lp :=0
- আরম্ভ করার জন্য i :=1, যখন i <ইনপুটের আকার, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −
- ইনপুট করার সময় [i] - input[lp]> mid, do −
- lp :=lp + 1
- tmp :=tmp + i - lp
- যদি tmp> =k হয়, তাহলে −
- ri :=মধ্য
- অন্যথায়
- le :=mid + 1
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& input, int k) {
k++;
sort(input.begin(), input.end());
int le = 0;
int ri = input.back() - input[0];
while (le < ri) {
int mid = (le + ri) / 2;
long long tmp = 0;
int lp = 0;
for (int i = 1; i < input.size(); i++) {
while (input[i] - input[lp] > mid) lp++;
tmp += i - lp;
}
if (tmp >= k)
ri = mid;
else
le = mid + 1;
}
return le;
}
int main() {
vector<int> numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <<endl;
return 0;
} ইনপুট
vector<int> numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <<endl; আউটপুট
2
