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

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

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

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

ป้อนข้อมูล

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

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

คำอธิบาย − ในที่นี้ k น้อยกว่า ดังนั้นตัวเลขอย่างน้อย 3 ตัวจึงมีผลรวมน้อยที่สุด

อย่างน้อย 3 ตัวเลข − 1,1,2 ผลรวม=4

ส่วนที่เหลือ Nk =5 หมายเลข:2,3,4,5,6 ผลรวม=20

ความแตกต่างสูงสุด :20-4 =16

ป้อนข้อมูล

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

คำอธิบาย − ที่นี่ k มากกว่า ดังนั้นตัวเลขสูงสุด 6 ตัวจะมีผลรวมมากที่สุด

ตัวเลขสูงสุด 6 ตัว − 8,8,7,4,4,4, ผลรวม=35

ส่วนที่เหลือ Nk =4 หมายเลข − 2,2,3,3 ผลรวม=10

ความแตกต่างสูงสุด − 35-10=

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ประกาศอาร์เรย์ของจำนวนเต็มซึ่งมีการเรียงลำดับแบบสุ่ม ( Arr[] )

• สร้างตัวแปรเพื่อเก็บขนาดของอาร์เรย์ (N)

• ฟังก์ชัน maxKDiff( int Arr[],int n, int k) ใช้เพื่อคำนวณความแตกต่างสูงสุด (maxD) ระหว่างดัชนีแรกและดัชนีสุดท้ายขององค์ประกอบในอาร์เรย์

• คำนวณผลรวมของอาร์เรย์ทั้งหมดและเก็บไว้ใน arrum

• สิ่งแรกคือการคำนวณผลรวมขององค์ประกอบอย่างน้อย k ใช้สำหรับวนซ้ำ ( i=0;i

  หาก k น้อยกว่า องค์ประกอบ k ที่เล็กที่สุดก็จะมีผลรวมน้อยที่สุด −

• ใน D1 เก็บ abs((ผลรวมของอาร์เรย์ทั้งหมด) - (2*ผลรวมขององค์ประกอบอย่างน้อย k)) สองครั้งเพราะผลรวมอาร์เรย์ก็มีองค์ประกอบเหล่านี้เช่นกัน

  k มีขนาดใหญ่กว่าองค์ประกอบ k ที่ใหญ่ที่สุดจะมีผลรวมสูงสุด −

• ใน D2 เก็บ abs((ผลรวมของอาร์เรย์ทั้งหมด) - (2*ผลรวมขององค์ประกอบ k สูงสุด)) สองครั้งเพราะผลรวมอาร์เรย์ก็มีองค์ประกอบเหล่านี้เช่นกัน

• เปรียบเทียบ D1 กับ D2 และเก็บค่าสูงสุดเป็น maxD

• คืนค่า maxD เป็นผลลัพธ์

ตัวอย่าง

#include #include // ฟังก์ชันสำหรับค้นหาความแตกต่างของกลุ่มสูงสุดของ arrayint maxKDiff (int arr[], int n, int k){ // ผลรวมของอาร์เรย์ int arrsum =0; int ฉัน; สำหรับ(i=0;i=D2?D1:D2; // return ค่าความแตกต่างสูงสุด return maxD;}// โปรแกรมควบคุมโปรแกรมหลัก main(){ int arr[] ={ 2,3,2,10,7,12,8}; int n =7; int k =3; เรียงลำดับ(arr,n); // เพื่อเรียงลำดับอาร์เรย์จากน้อยไปมาก printf("ความแตกต่างสูงสุดระหว่างกลุ่มขององค์ประกอบ k และส่วนที่เหลือของอาร์เรย์ :%d" , maxKDiff(arr,n,k)); คืนค่า 0;}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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