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