home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Count pairs (x, y) in an array such that x < y in C++

กำหนด array หาจำนวนคู่ (x,y) ที่ x < y (พิจารณาคู่สั่งลำดับ ordered pairs)

ตัวอย่าง: {2,4,3,1} → Output: 6

คู่: (2,4),(2,3),(3,4),(1,2),(1,3),(1,4)

วิธีแก้ปัญหา

O(n²) - Brute Force

วนลูป i, j ทุกคู่ นับที่ arr[i] < arr[j]

O(n log n) - Sort + Binary Search / Fenwick Tree

  1. Compress ค่า (coordinate compression)
  2. ใช้ Fenwick Tree นับจำนวนค่าที่น้อยกว่า

ตัวอย่างโค้ด C++ (Simple O(n²))

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

int X_Less_Y(int arr[], int n) {
    int count = 0;
    for(int i=0;i

Input

{2,4,3,1}

Output

6