মান লক্ষ্য করুন দুটি সংখ্যা s এবং t, এবং আরেকটি n এলিমেন্টের অ্যারে D। ড্রিমল্যান্ড সাবওয়ের সার্কুলার লাইনে n টি ভিন্ন স্টেশন আছে। আমরা সব পেয়ার ভেবর স্টেশনের দূরত্ব জানি: D[i] হলো স্টেশন i এবং i+1-এর মধ্যে দূরত্ব, এবং D[n-1] হলো (n-1) এবং ০ নম্বর স্টেশনের মধ্যে দূরত্ব। আমাদের s থেকে t-তে শর্টেস্ট ডিস্ট্যান্স বের করতে হবে।
তাই, যদি ইনপুট হয় s = 1; t = 3; D = [2, 3, 4, 9], তবে আউটপুট হবে ৫।
ধাপসমূহ
এটি সমাধান করার জন্য, আমরা এই ধাপগুলো অনুসরণ করব −
n := size of D
Define an array arr of size (n + 1), and fill with 0
for initialize i := 1, when i <= n, update (increase i by 1), do:
arr[i] := D[i - 1]
sum1 := sum1 + arr[i]
if s > t, then:
swap s and t
for initialize i := s, when i < t, update (increase i by 1), do:
sum2 := sum2 + arr[i]
return minimum of sum2 and (sum1 - sum2)
উদাহরণ
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখি −
#include <bits/stdc++.h>
using namespace std;
int solve(int s, int t, vector<int> D){
int n = D.size(), sum1 = 0, sum2 = 0;
vector<int> arr(n + 1, 0);
for (int i = 1; i <= n; i++){
arr[i] = D[i - 1];
sum1 += arr[i];
}
if (s > t)
swap(s, t);
for (int i = s; i < t; i++)
sum2 += arr[i];
return min(sum2, sum1 - sum2);
}
int main(){
int s = 1;
int t = 3;
vector<int> D = { 2, 3, 4, 9 };
cout << solve(s, t, D) << endl;
}
ইনপুট
1, 3, { 2, 3, 4, 9 }
আউটপুট
5
