สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n พิจารณาว่ามีหอคอยบล็อกอยู่ n ตึกติดต่อกัน หอคอย ith มีความสูง A[i] ในวันเดียว เราสามารถดำเนินการได้:เลือกสองดัชนี i และ j (i !=j) และย้ายกลับจากหอคอย i ไปยัง j มันจะลด A[i] ลง 1 และเพิ่ม A[j] ขึ้น 1 ความอัปลักษณ์ของสิ่งปลูกสร้างคือ max(A) − min(A) เราต้องหาความอัปลักษณ์ให้น้อยที่สุดเท่าที่จะทำได้
ดังนั้น ถ้าอินพุตเป็น A =[1, 2, 3, 1, 5] ผลลัพธ์จะเป็น 1 เพราะเราสามารถดำเนินการได้สามอย่างสำหรับ 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 := size of A for initialize i := 0, when i < n, update (increase i by 1), do: sum := sum + A[i] if sum mod n is same as 0, then: return 0 return 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
