मान लीजिए कि हमारे पास एन तत्वों के साथ एक सरणी डी है। विचार करें कि एक कोड उत्सव में अमल सहित N+1 प्रतिभागी हैं। अमल ने जाँच की और पाया कि उसके शहर में स्थानीय समय और i-th व्यक्ति के शहर के बीच का समय अंतराल D[i] घंटे था। दो शहरों के बीच का समय अंतराल:किन्हीं दो शहरों ए और बी के लिए, यदि शहर बी में स्थानीय समय उस समय है जब शहर ए में स्थानीय समय 0 बजे है, तो इन दोनों के बीच का समय अंतराल शहर न्यूनतम d और 24-d घंटे हैं।
यहां, हम 24 घंटे के नोटेशन का उपयोग कर रहे हैं। फिर, N+1 लोगों में से चुने गए दो लोगों की प्रत्येक जोड़ी के लिए, उन्होंने उनके शहरों के बीच के समय के अंतराल को लिखा। माना उनमें से सबसे छोटा समय अंतराल s घंटे है। हमें s का अधिकतम संभव मान ज्ञात करना है।
इसलिए, यदि इनपुट D =[7, 12, 8] जैसा है, तो आउटपुट 4 होगा, क्योंकि दूसरे और तीसरे व्यक्ति के शहरों के बीच का समय अंतराल 4 घंटे है।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
n := size of D
sort the array D
Define an array t
insert 0 at the end of t
for initialize i := 0, when i < n, update (increase i by 1), do:
if i mod 2 is same as 0, then:
insert D[i] at the end of t
Otherwise
insert 24 - D[i] at the end of t
sort the array t
ans := inf
for initialize i := 1, when i < size of t, update (increase i by 1), do:
ans := minimum of ans and t[i] - t[i - 1]
return ans उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> D) {
int n = D.size();
sort(D.begin(), D.end());
vector<int> t;
t.push_back(0);
for (int i = 0; i < n; i++){
if (i % 2 == 0)
t.push_back(D[i]);
else
t.push_back(24 - D[i]);
}
sort(t.begin(), t.end());
int ans = 1e9;
for (int i = 1; i < t.size(); i++){
ans = min(ans, t[i] - t[i - 1]);
}
return ans;
}
int main(){
vector<int> D = { 7, 12, 8 };
cout << solve(D) << endl;
} इनपुट
{ 7, 12, 8 }
आउटपुट
4