สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และอีกจำนวนหนึ่งเป็น m เราต้องตรวจสอบว่าเราสามารถจัดเรียงอาร์เรย์ใหม่ในลักษณะที่
$$\mathrm{\sum_{i=1}^{n} \sum_{j=1}^{n}\frac{A[j]}{j} =m}$$
จะไม่มีการปัดเศษในการดำเนินการ A[j]/j
ดังนั้น ถ้าอินพุตเป็น A =[2, 5, 1]; m =8 แล้วผลลัพธ์จะเป็น True เพราะสำหรับการจัดเรียงของ [1, 2, 5] (1/1 + 2/2 + 5/3) + (2/2 + 5/3) + (5 /3) =8
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
sum := 0 n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: sum := sum + A[i] if sum is same as m, then: return true Otherwise return false
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int m) {
long sum = 0;
int n = A.size();
for (int i = 0; i < n; ++i) {
sum += A[i];
}
if (sum == m)
return true;
else
return false;
}
int main() {
vector<int> A = { 2, 5, 1 };
int m = 8;
cout << solve(A, m) << endl;
} อินพุต
{ 2, 5, 1 }, 8 ผลลัพธ์
1
