Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chương trình C++ đếm số cặp thỏa mãn điều kiện hiệu bằng tổng

Mô tả bài toán

Cho mảng nums kích thước n. Tìm số cặp (i,j) (i) sao cho j - i = nums[i] + nums[j].

Ví dụ

n=8, nums={4,2,1,0,1,2,3,3}. Đầu ra: 13.

Thuật toán (Biến đổi + Binary Search)

  1. Điều kiện j - i = nums[i] + nums[j] ⇔ j - nums[j] = i + nums[i].
  2. Tạo mảng vals[i] = i+1 - nums[i] (chỉ số 1-based). Sắp xếp vals.
  3. Với mỗi i, tính k = nums[i] + i + 1. Số j thỏa mãn bằng upper_bound(vals, k) - lower_bound(vals, k).
  4. Tổng cộng là kết quả.

Đoạn mã C++

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

int solve(int n, vector<int> nums) {
    vector<int> vals(n);
    for(int i=0;i

Đầu vào / Đầu ra

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

Output: 13