ความต่างสูงสุดระหว่างกลุ่ม k องค์ประกอบและส่วนที่เหลือของอาร์เรย์ในภาษา C

เราได้รับอาร์เรย์ของจำนวนเต็มขนาด N และตัวเลข k อาร์เรย์ประกอบด้วยจำนวนเต็มเรียงลำดับสุ่ม งานคือหาความต่างสูงสุดระหว่างกลุ่ม k องค์ประกอบและส่วนที่เหลือของอาร์เรย์ อาร์เรย์จะถูกแบ่งเป็นสองส่วน ส่วนแรกคือกลุ่ม k องค์ประกอบที่นำออกไป และส่วนที่สองคือองค์ประกอบที่เหลือของอาร์เรย์ เราต้องเลือก k องค์ประกอบ使得ความต่างของผลรวมองค์ประกอบในทั้งสองกลุ่มเป็นค่าสูงสุด

ถ้า k เล็กกว่า (<= ครึ่งหนึ่งของขนาดอาร์เรย์) k องค์ประกอบที่น้อยที่สุดจะมีผลรวมน้อยที่สุด และ N-k องค์ประกอบที่เหลือจะมีผลรวมมากที่สุด ดังนั้นความต่างสูงสุดคือ — (ผลรวมของ N-k องค์ประกอบที่เหลือ) - (ผลรวมของ k องค์ประกอบที่น้อยที่สุด)

ถ้า k ใหญ่กว่า (> ครึ่งหนึ่งของขนาดอาร์เรย์) k องค์ประกอบที่มากที่สุดจะมีผลรวมมากที่สุด และ N-k องค์ประกอบที่เหลือจะมีผลรวมน้อยที่สุด ดังนั้นความต่างสูงสุดคือ (ผลรวมของ k องค์ประกอบที่มากที่สุด) - (ผลรวมของ N-k องค์ประกอบที่เหลือ)

ตัวอย่าง

อินพุต

Arr[] = { 2, 5, 6, 1, 3, 2, 1, 4 } k = 3

เอาต์พุต — ความต่างสูงสุดระหว่างกลุ่ม k องค์ประกอบและส่วนที่เหลือของอาร์เรย์ — 16

อินพุต

Arr[] = { 2, 2, 3, 4, 8, 3, 4, 4, 8, 7 } k = 6

เอาต์พุต — ความต่างสูงสุดระหว่างกลุ่ม k องค์ประกอบและส่วนที่เหลือของอาร์เรย์ — 25

วิธีการที่ใช้ในโปรแกรม

• ประกาศอาร์เรย์จำนวนเต็มที่มีตัวเลขเรียงลำดับสุ่ม (Arr[])
• สร้างตัวแปรเก็บขนาดอาร์เรย์ (N)
• ฟังก์ชัน maxKDiff(int Arr[], int n, int k) ใช้คำนวณความต่างสูงสุด (maxD) ระหว่างกลุ่มแรกและสุดท้ายขององค์ประกอบในอาร์เรย์
• คำนวณผลรวมของอาร์เรย์ทั้งหมดและเก็บใน arrsum
• คำนวณผลรวมของ k องค์ประกอบที่น้อยที่สุด ด้วยลูป for (i=0; i
• ใน D1 เก็บ abs((ผลรวมอาร์เรย์ทั้งหมด) - (2*ผลรวม k องค์ประกอบน้อยที่สุด)) คูณ 2 เพราะผลรวมอาร์เรย์ก็มีองค์ประกอบเหล่านี้อยู่ด้วย
• คำนวณผลรวมของ k องค์ประกอบที่มากที่สุด
• ใน D2 เก็บ abs((ผลรวมอาร์เรย์ทั้งหมด) - (2*ผลรวม k องค์ประกอบมากที่สุด))
• เปรียบเทียบ D1 กับ D2 และเก็บค่าสูงสุดใน maxD
• คืนค่า maxD เป็นผลลัพธ์

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

#include <stdio.h>
#include <math.h>

// ฟังก์ชันหาความต่างกลุ่มสูงสุดของอาร์เรย์
int maxKDiff(int arr[], int n, int k) {
    // ผลรวมของอาร์เรย์
    int arrsum = 0;
    int i;
    for(i = 0; i < n; i++)
        arrsum += arr[i];
    
    // ผลรวมของ k ตัวน้อยที่สุด
    int sumk = 0;
    for(i = 0; i < k; i++)
        sumk += arr[i];
    
    // ความต่างสำหรับ k ตัวน้อยที่สุด
    int D1 = abs(arrsum - 2 * sumk);
    
    // ผลรวมของ k องค์ประกอบมากที่สุด
    sumk = 0;
    int j = 0;
    for(i = n - 1; j < k; i--) {
        sumk += arr[i];
        j++;
    }
    
    // ความต่างสำหรับ k ตัวมากที่สุด
    int D2 = abs(arrsum - 2 * sumk);
    int maxD = D1 >= D2 ? D1 : D2;
    
    // คืนค่าความต่างสูงสุด
    return maxD;
}

// โปรแกรมหลัก
int main() {
    int arr[] = { 2, 3, 2, 10, 7, 12, 8 };
    int n = 7;
    int k = 3;
    sort(arr, n); // เรียงอาร์เรย์จากน้อยไปมาก
    printf("ความต่างสูงสุดระหว่างกลุ่ม k องค์ประกอบและส่วนที่เหลือของอาร์เรย์: %d", maxKDiff(arr, n, k));
    return 0;
}

ผลลัพธ์

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้ —

ความต่างสูงสุดระหว่างกลุ่ม k องค์ประกอบและส่วนที่เหลือของอาร์เรย์: 30