home

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

ผลรวมอาร์เรย์สูงสุดที่สามารถรับได้หลังจากการเปลี่ยนแปลง k ใน C++

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

วิธีที่ใช้จะแปลงทุกจำนวนลบเป็นบวก หากมีตัวเลขติดลบ N สำหรับสิ่งนี้ เราจะจัดเรียงอาร์เรย์ -

  • ถ้า N

  • ตอนนี้ถ้า K-N เป็นเลขคู่สำหรับสัญญาณการเปลี่ยนแปลงของ K-N ที่เหลืออยู่จะไม่มีผลอะไรอย่าทำอะไรเลย

  • ถ้า K-N เป็นเลขคี่ สำหรับการดำเนินการ K-N ที่เหลือ ให้เปลี่ยนเครื่องหมายของจำนวนที่น้อยที่สุด (ซึ่งจะกลายเป็นค่าลบ) แต่ผลรวมทั้งหมดจะสูงสุด

    หรือ

    ถ้า N>K เปลี่ยนเครื่องหมายของตัวเลขลบ K และเพิ่มอาร์เรย์ ผลรวมจะสูงสุด

อินพุต

Arr[]={ 0,-2,6,4,8,2,-3 } K=4

ผลลัพธ์

ผลรวมอาร์เรย์สูงสุดคือ :25

คำอธิบาย − การเปลี่ยนแปลง 4 องค์ประกอบคือ

<ก่อน>1. 0,2,6,4,8,2,-3 -2 เปลี่ยนเป็น 22. 0,2,6,4,8,2,3 -3 เปลี่ยนเป็น 33. 0,-2,6,4,8, 2,3 2 เปลี่ยนเป็น -24 0,2,6,4,8,2,3 -2 เปลี่ยนเป็น 2ผลรวมสูงสุดคือ 25

อินพุต

Arr[]={ -1,-2,-3,-4,-5,-6,-7 } K=4

ผลลัพธ์

ผลรวมอาร์เรย์สูงสุดคือ :16

คำอธิบาย − การเปลี่ยนแปลง 4 องค์ประกอบคือ

<ก่อน>1. -1,-2,-3,-4,-5,-6,7 -7 เปลี่ยนเป็น 72. -1,-2,-3,-4,-5,6,7 -6 เปลี่ยนเป็น 63. - 1,-2,-3,-4,5,6,7 -5 เปลี่ยนเป็น 54 -1,-2,-3,4,5,6,7 -4 เปลี่ยนเป็น 4ผลรวมสูงสุดคือ 16

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

  • อาร์เรย์จำนวนเต็ม Arr[] ใช้เพื่อเก็บจำนวนเต็ม

  • จำนวนเต็ม 'ขนาด' เก็บความยาวของอาร์เรย์และ K ถูกเตรียมใช้งาน

  • ฟังก์ชัน returnSum( int arr[], int n, int k) รับอาร์เรย์ ขนาด และ k เป็นอินพุตและส่งกลับผลรวมสูงสุดขององค์ประกอบหลังจากดำเนินการ k แล้ว

  • ก่อนอื่นเราจะจัดเรียงอาร์เรย์โดยใช้ sort(arr,arr+n)

  • ตอนนี้เราจะใช้การดำเนินการ arr[i]*-1 กับองค์ประกอบเชิงลบทั้งหมดจนกว่าจะถึงดัชนีสุดท้ายหรือ k กลายเป็น 0

  • หาก k น้อยกว่าจำนวนองค์ประกอบเชิงลบ ขั้นตอนข้างต้นจะเปลี่ยนองค์ประกอบ k -ve

  • หาก k มากกว่า และค่าที่เหลือของ k จะถูกตรวจสอบว่าเป็นคี่หรือคู่

  • หาก k เหลือเป็นเลขคี่ เราจะเปลี่ยนค่าขององค์ประกอบขั้นต่ำโดยใช้การดำเนินการ arr[i]*-1 หนึ่งครั้ง โดยที่ arr[i] จะพบอย่างน้อย (คูณด้วย -1 คี่เท่ากับทำครั้งเดียว)

  • หาก k เหลือเป็นคู่ arr[i]*-1 จะไม่มีผลใดๆ ไม่ทำอะไรเลย

  • คำนวณผลรวมของอาร์เรย์ทั้งหมดแล้วส่งคืนผลลัพธ์

ตัวอย่าง

#include ใช้เนมสเปซ std;int returnSum(int arr[], int n, int k){ // จัดเรียงองค์ประกอบอาร์เรย์ sort (arr, arr + n); // เปลี่ยนสัญญาณขององค์ประกอบเชิงลบ // เริ่มจากที่เล็กที่สุด // การวนซ้ำนี้จะเปลี่ยนเครื่องหมายขององค์ประกอบ -ve // ​​สำหรับแต่ละองค์ประกอบ k one -ve จะถูกเปลี่ยนเป็นค่าบวกสำหรับ (i=0;i0 &&arr[i]<0){ arr[i]=arr[i]*-1; k--;}//ถ้า k ไม่ใช่ศูนย์และเครื่องหมายการเปลี่ยนแปลงคี่ขององค์ประกอบขั้นต่ำ // ครั้งเดียวเหมือนกับการเปลี่ยนเครื่องหมายคี่ timesif (k % 2 ==1) { int min =arr[0]; int pos=0; //index ขององค์ประกอบขั้นต่ำสำหรับ (i =1; i  
ผลลัพธ์
 
ผลรวมอาร์เรย์สูงสุดที่สามารถรับได้หลังจากการเปลี่ยนแปลง k ทั้งหมด :24