{"id":34044,"date":"2024-11-01T09:23:29","date_gmt":"2024-11-01T09:23:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34044"},"modified":"2024-11-01T10:53:52","modified_gmt":"2024-11-01T10:53:52","slug":"c-coding-test-course-calculating-the-amount-of-water","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34044\/","title":{"rendered":"C# Coding Test Course, Calculating the Amount of Water"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

\n There is a tank that can hold water in a specific area. Each wall of the tank has a different height. When it rains, water will accumulate, and the problem is to determine how much water can be held between each wall.\n <\/p>\n

Input<\/h3>\n

\n The first line contains an integer N (1 \u2264 N \u2264 100,000). N represents the number of walls.
\n The second line contains N integers h_i (1 \u2264 h_i \u2264 1,000,000), which represent the height of each wall.\n <\/p>\n

Output<\/h3>\n

\n Print the amount of water that can be held on one line.\n <\/p>\n

Example Problem<\/h2>\n
\nExample Input:<\/strong>
\n 5
\n 0 1 0 2 1 0 1 3 2 1 2 1
\nExample Output:<\/strong>
\n 6\n <\/div>\n

Problem Solving Process<\/h2>\n

\n To solve this problem, we will use two arrays. One will store the maximum height of walls to the left of the current position, and the other will store the maximum height of walls to the right.\n <\/p>\n

1. Problem Analysis<\/h3>\n

\n The amount of water that can be held at each position is the difference between the minimum of the maximum heights of the walls on the left and right, and the current wall height.
\n For example, the amount of water at position i can be calculated as follows:
\n water[i] = max(0, min(left_max[i], right_max[i]) - height[i])<\/code>
\n where left_max<\/code> represents the maximum height of walls to the left of i, and right_max<\/code> represents the maximum height of walls to the right.\n <\/p>\n

2. Algorithm Design<\/h3>\n

\n We can design the algorithm in the following steps:<\/p>\n

    \n
  1. Receive the input.<\/li>\n
  2. Create an array left_max<\/code> to store the maximum heights of the left walls.<\/li>\n
  3. Create an array right_max<\/code> to store the maximum heights of the right walls.<\/li>\n
  4. Calculate the amount of water that can be held at each position.<\/li>\n
  5. Finally, output the total amount of water.<\/li>\n<\/ol>\n

    3. Code Implementation<\/h3>\n

    \n Below is the code that implements the above algorithm in C#.\n <\/p>\n

    \nusing System;\n\nclass Program\n{\n    static void Main(string[] args)\n    {\n        int N = int.Parse(Console.ReadLine());\n        int[] height = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n\n        \/\/ Left maximum height array\n        int[] left_max = new int[N];\n        left_max[0] = height[0];\n\n        for (int i = 1; i < N; i++)\n        {\n            left_max[i] = Math.Max(left_max[i - 1], height[i]);\n        }\n\n        \/\/ Right maximum height array\n        int[] right_max = new int[N];\n        right_max[N - 1] = height[N - 1];\n\n        for (int i = N - 2; i >= 0; i--)\n        {\n            right_max[i] = Math.Max(right_max[i + 1], height[i]);\n        }\n\n        \/\/ Calculate the amount of water\n        int water = 0;\n        for (int i = 0; i < N; i++)\n        {\n            water += Math.Max(0, Math.Min(left_max[i], right_max[i]) - height[i]);\n        }\n\n        Console.WriteLine(water);\n    }\n}\n    <\/code><\/pre>\n
    4. Code Explanation<\/h3>\n
    \n        The algorithm used in the above C# code is as follows:<\/p>\n