Δεδομένου ενός ταξινομημένου πίνακα και ενός αριθμού x, βρείτε το ζεύγος σε πίνακα του οποίου το άθροισμα είναι πλησιέστερο στο x


ΑΛΓΟΡΙΘΜΟΣ

ΣΥΜΠΕΡΙΦΟΡΑ ΧΡΟΝΟΥ: ΕΠΙ)

ΣΥΜΠΕΡΑΣΤΗΡΙΟ ΧΩΡΟΥ: Ο (1)

1. Αρχικοποιούμε δύο δείκτες όπως μεταβλητή αριστερά και δεξιά, τα οποία βρίσκονται στην αρχή και στο τέλος της ταξινομημένης συστοιχίας αντίστοιχα.

2. Παίρνουμε την πλησιέστερη μεταβλητή που αποθηκεύει την απόλυτη ελάχιστη απόκλιση από έναν δεδομένο αριθμό X και μια άλλη μεταβλητή που ονομάζεται terdekat_sum που αποθηκεύει το πραγματικό πλησιέστερο άθροισμα στο X.

3. Βγαίνουμε μέσω του πίνακα ως εξής:

ένα. άθροισμα = arr [αριστερά] + arr [δεξιά]

σι. εάν οι abs (άθροισμα - X) είναι μικρότεροι από το παρόν πλησιέστερο, ενημερώστε το και αποθηκεύστε επίσης το άθροισμα στο

ντο. αλλιώς ελέγξτε αν το άθροισμα> X και μετά μειώστε τη σωστή μεταβλητή

ρε. αλλιώς εάν το άθροισμα <= X αυξήστε τη αριστερή μεταβλητή

ΕΙΣΑΓΩΓΗ:

Παράταξη: 4 16 28 37 42 56 63 89 124 245

Αριθμός: 101

ΠΑΡΑΓΩΓΗ:

100 (άθροισμα 63 και 37)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[]= {14,16,19,21,46,84,126,169};
	int N = sizeof(arr)/sizeof(arr[0]);
	
	int x;
	cin>>x; // the number to which closest sum is to be found
	
	//left and right pointing at start and end of the sorted array
	int left = 0, right = N-1, sum = 0, closest = INT_MAX , closest_sum; 
	
	//sum to store sum , closest to store the minimum difference found and closest_sum to store the actual value closest to x
	while(left < right)
	{
		sum = arr[left] + arr[right];
		if(abs(x -sum) < closest)
		{
			closest = abs(x -sum);
			closest_sum = sum;
		}
		if(sum > x)
			right--;
		else if(sum <= x)
			left++;
	}
	cout<<closest_sum<<endl;
}

Δοκίμασέ το