Chương trình C ++ để tìm ra số cặp trong một mảng thỏa mãn một điều kiện nhất định

Giả sử, chúng ta được cung cấp n số trong số mảng. Chúng ta phải chọn một cặp hai số từ mảng và có điều kiện là hiệu số vị trí của chúng trong mảng bằng tổng của hai số đó. Có thể có tổng n (n - 1) / 2 tổng số cặp từ dãy số đã cho. Chúng ta phải tìm ra tổng số các cặp như vậy từ mảng.

Vì vậy, nếu đầu vào là n =8, nums ={4, 2, 1, 0, 1, 2, 3, 3}, thì đầu ra sẽ là 13.

Có thể có 13 cặp như vậy trong mảng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Define an array vals(n)
for initialize i := 0, when i < n, update (increase i by 1), do:
   vals[i] := i + 1 - nums[i]
sort the array vals
res := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   k := nums[i] + i + 1
res := res + (position of first occurrence of a value not less than k in array vals - position of first occurrence of a value not greater than k in array vals)
return res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

int solve(int n, vector<int> nums){
   vector<int> vals(n);
   for( int i = 0; i < n; i++)
      vals[i] = i + 1 - nums[i]; 
   sort(vals.begin(), vals.end());
   int res = 0;
   for( int i = 0; i < n; i++ ) {
      int k = nums[i] + i + 1;
      res += upper_bound(vals.begin(), vals.end(), k) - lower_bound(vals.begin(), vals.end(), k);
   }
   return res;
}
int main() {
   int n = 8;
   vector<int> nums = {4, 2, 1, 0, 1, 2, 3, 3};
   cout<< solve(n, nums);
   return 0;
}

Đầu vào

8, {4, 2, 1, 0, 1, 2, 3, 3}

Đầu ra

13