สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และอีกจำนวนหนึ่งคือ k มีกองขนมจำนวน n กอง กอง ith มีจำนวนลูกอม A[i] เราสามารถดำเนินการกับสองดัชนี iand j (i !=j) จากนั้นเพิ่มจำนวนลูกอม A[i] อีกจำนวนหนึ่งให้กับ A[i] (A[i] จะไม่ลดลง) เราสามารถดำเนินการนี้ได้หลายครั้ง แต่น่าเสียดายที่บางกองมีมากกว่า k แคนดี้ เราไม่สามารถดำเนินการได้อีกต่อไป เราต้องหาจำนวนครั้งสูงสุดที่จะดำเนินการนี้ได้
ดังนั้น ถ้าอินพุตเป็น A =[1, 2, 3]; k =5 แล้วผลลัพธ์จะเป็น 5 เพราะเราสามารถหา i =0 และสำหรับ j =1 เราสามารถทำได้สามครั้ง และสำหรับ j =2 เราสามารถทำได้สองครั้ง รวมแล้ว 5 ครั้ง
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ans := 0 n := size of A sort the array A for initialize i := 1, when i < n, update (increase i by 1), do: ans := ans + (k - A[i]) return ans
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k){
int ans = 0;
int n = A.size();
sort(A.begin(), A.end());
for (int i = 1; i < n; i++){
ans += (k - A[i]) / A[0];
}
return ans;
}
int main(){
vector<int> A = { 1, 2, 3 };
int k = 5;
cout << solve(A, k) << endl;
} อินพุต
{ 1, 2, 3 }, 5 ผลลัพธ์
5
