สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ และตัวเลข m มีนักเรียน n คนสอบ คะแนนสูงสุดคือ m A[i] คือคะแนนของนักเรียนคนที่ i เราสามารถปรับคะแนนนักเรียนแต่ละคนได้ แต่ต้องปฏิบัติตามเงื่อนไข: คะแนนไม่เกิน m คะแนนทั้งหมดเป็นจำนวนเต็ม และคะแนนเฉลี่ยของนักเรียนทั้งหมดไม่เปลี่ยนแปลง หากเราต้องการเพิ่มคะแนนนักเรียนคนแรกให้มากที่สุด คะแนนสูงสุดที่เป็นไปได้คือเท่าไหร่
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [1, 2, 3, 4]; m = 10 ผลลัพธ์จะได้ 10 เพราะค่าเฉลี่ยคือ 2.5 เราสามารถตั้งคะแนนเป็น [10, 0, 0, 0] ซึ่งค่าเฉลี่ยเท่าเดิมแต่นักเรียนคนแรกได้คะแนนสูงสุด
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
sum := 0 n := ขนาดของ A สำหรับ j := 0 เมื่อ j < n เพิ่ม j ทีละ 1 ทำ: sum := sum + A[j] คืนค่า min(m, sum)
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A, int m){ int sum = 0; int n = A.size(); for (int j = 0; j < n; j++){ sum += A[j]; } return min(m, sum); } int main(){ vector<int> A = { 1, 2, 3, 4 }; int m = 10; cout << solve(A, m) << endl; }
ข้อมูลนำเข้า
{ 1, 2, 3, 4 }, 10
ข้อมูลส่งออก
10
