จัดเรียงอาร์เรย์เพื่อลดผลรวมผลคูณคู่ติดกันให้น้อยที่สุดใน C++

ภาพรวม

ได้รับอาร์เรย์จำนวนเต็มบวก arr[] งานคือจัดเรียงใหม่ให้เมื่อนำอิลิเมนต์คู่อิลิเมนต์ถัดไป (Consecutive pairs) มาคูณกัน แล้วบวกผลรวมทั้งหมด จะได้ผลรวมที่น้อยที่สุด

ตัวอย่าง

อินพุต − int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}

เอาต์พุต − Rearrangement of an array to minimize sum i.e. 7 of product of consecutive pair elements is: 7 0 5 0 5 1 2 1

คำอธิบาย − จัดเรียงเป็น 7 0 5 0 5 1 2 1 ตรวจสอบ: 7×0 + 5×0 + 5×1 + 2×1 = 0+0+5+2 = 7

อินพุต − int arr[] = {1, 3, 7, 2, 4, 3}

เอาต์พุต − Rearrangement of an array to minimize sum i.e. 24 of product of consecutive pair elements is: 7 1 4 2 3 3

คำอธิบาย − จัดเรียงเป็น 7 1 4 2 3 3 ตรวจสอบ: 7×1 + 4×2 + 3×3 = 7+8+9 = 24

แนวทางการแก้ปัญหา

• รับอาร์เรย์ คำนวณขนาด
• เรียงลำดับอาร์เรย์ด้วย sort()
• เรียก Rearrange_min_sum(arr, size)
• ภายในฟังก์ชัน:
  • สร้าง vector even, odd
  • temp = 0, total = 0
  • วน i=0 ถึง size-1: หาก i < size/2 push เข้า odd มิฉะนั้น push เข้า even
  • เรียง even เรียงจากมากไปน้อย sort(even.begin(), even.end(), greater<int>())
  • วน j=0 ถึง even.size()-1: arr[temp++] = even[j]; arr[temp++] = odd[j]; total += even[j] * odd[j]
  • คืนค่า total
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

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

int Rearrange_min_sum(int arr[], int size){ 
    vector<int> even, odd; 
    int temp = 0; 
    int total = 0; 
    for(int i = 0; i < size; i++){ 
        if (i < size/2){ 
            odd.push_back(arr[i]); 
        } else { 
            even.push_back(arr[i]); 
        } 
    } 
    sort(even.begin(), even.end(), greater<int>()); 
    for(int j = 0; j < even.size(); j++){ 
        arr[temp++] = even[j]; 
        arr[temp++] = odd[j]; 
        total += even[j] * odd[j]; 
    } 
    return total; 
} 

int main(){ 
    int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    sort(arr, arr + size); 
    int total = Rearrange_min_sum(arr, size); 
    cout << "Rearrangement of an array to minimize sum i.e. " << total << " of product of consecutive pair elements is: "; 
    for(int i = 0; i < size; i++){ 
        cout << arr[i] << " "; 
    } 
    return 0; 
}

ผลลัพธ์

Rearrangement of an array to minimize sum i.e. 7 of product of consecutive pair elements is: 7 0 5 0 5 1 2 1