คอนเทนเนอร์ที่มีน้ำมากที่สุดใน C++

เราได้รับความสูงของผนังตู้คอนเทนเนอร์ เป้าหมายคือการหาภาชนะที่สามารถบรรจุน้ำได้ในปริมาณสูงสุด เนื่องจากความสูงของผนังเป็นองค์ประกอบของอาร์เรย์ ระยะห่างระหว่างกำแพงจึงถือเป็นความกว้างระหว่างผนังทั้งสอง ตัวอย่างเช่น ผนังที่มีความสูง Arr[i] และ Arr[j] มีความกว้างระหว่าง ji ( 0<=i

ดังนั้นความสูงของน้ำจะขึ้นกับความสูงที่น้อยกว่า ถ้า Arr[i]

เราต้องหาพื้นที่ดังกล่าวให้ได้มากที่สุด

อินพุต

Arr[]= { 5,1,2,3,5 }

ผลลัพธ์

Maximum water area : 20

คำอธิบาย

ดังรูป สำหรับผนังสูง 5,1,2,3 และความกว้างสูงสุดระหว่างผนัง

Arr[0] and Arr[4] width=4, area = Arr[0]<=Arr[4] → 5*4=20
Arr[1] and Arr[4] width=3, area = Arr[1]<=Arr[4] → 1*4=4
Arr[2] and Arr[0] or Arr[4] width=4, area = Arr[0]<=Arr[0] → 2*2=4
Arr3] and Arr[0] width=3, area = Arr[0]<=Arr[0] → 3*3=9
Arr[4] and Arr[0] width=4, area = Arr[0]<=Arr[4] → 5*4=20

พื้นที่บรรจุสูงสุดจะมีน้ำสูงสุด พื้นที่=20 ผนัง Arr[0] และ Arr[4]

อินพุต

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

ผลลัพธ์

Maximum water area : 16

คำอธิบาย

Arr[0] and Arr[5] width=5, area = Arr[0]<=Arr[5] → 1*5= 5
Arr[1] and Arr[5] width=4, area = Arr[1]<=Arr[5] → 4*4=16
Arr[2] and Arr[5] width=3, area = Arr[2]<=Arr[5] → 3*4=12
Arr[3] and Arr[1] width=2, area = Arr[3]<=Arr[1] → 3*2=6
Arr[4] and Arr[1] width=3, area = Arr[1]<=Arr[4] → 2*3=6
Arr[5] and Arr[1] width=4, area = Arr[1]<=Arr[4] → 4*4=16

พื้นที่บรรจุสูงสุดจะมีน้ำสูงสุด พื้นที่=16 ผนัง Arr[0] และ Arr[4]

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

• ผนังอาร์เรย์จำนวนเต็ม[] มีความสูงของผนัง

• ฟังก์ชัน mostwater(int A[], int len) รับค่าความสูงและค่าจำนวน ขององค์ประกอบในนั้นและส่งคืนพื้นที่ของภาชนะที่มีน้ำมากที่สุดเนื่องจากมีเพียงความสูงและความกว้างเท่านั้น

• เราใช้ดัชนีสองตัว r=len-1 และ l=0 เพื่อเริ่มสำรวจอาร์เรย์จากปลายทั้งสองข้าง

• พื้นที่จำนวนเต็มและ maxarea ใช้เพื่อเก็บพื้นที่ของคอนเทนเนอร์ปัจจุบันและพื้นที่คอนเทนเนอร์สูงสุดที่พบจนถึงตอนนี้ตามลำดับ เริ่มแรก 0

• int minwall,lwall,rwall เก็บความสูงของผนังด้านซ้าย ( A[l] ), ผนังด้านขวา ( A[r] ) และความสูงขั้นต่ำของ lwall และ rwall;

• ในขณะที่ ( l

• ความกว้างระหว่างสองผนังคือความแตกต่างของดัชนี ( r-l )

• คำนวณพื้นที่ของน้ำ/ภาชนะเป็น minwall* ( r-l ) และปรับปรุงพื้นที่

• ทำเช่นนี้กับวอลล์ทั้งหมด หากพื้นที่ปัจจุบันสูงสุดแล้วให้อัปเดต maxarea

• ในท้ายที่สุด maxarea จะมีพื้นที่ที่ต้องการของภาชนะที่มีน้ำมากที่สุด

• คืนค่า maxarea ตามผลลัพธ์

ตัวอย่าง

#include<iostream>
using namespace std;
int mostwater(int A[], int len){
   int r=len-1; //index of right wall of container
   int l=0; //index of left wall of container
   int area=0,maxarea=0;
   int minwall,lwall,rwall;
   // int area = 0;
   while (l < r){
      // Calculating the max area
      lwall = A[l]; //height of left wall of container
      rwall =A[r]; //height of right wall of container
      minwall=lwall<=rwall?lwall:rwall; //min. of two walls is height of water
      area=minwall*(r-l); // area is min wall* widht(r-l)
      maxarea=area>=maxarea?area:maxarea;
      if (l < r)
         l += 1;
      else
         r -= 1;
   }
   return maxarea;
}
int main(){
   int walls[] = {1, 5, 4, 3, 2, 4};
   int num = sizeof(walls) / sizeof(walls[0]);
   cout << endl <<"Container with Most water has area:"<< mostwater(walls,num);
}

ผลลัพธ์

Container with Most water has area:16