ภาพรวม
โจทย์สร้างอาร์เรย์ขนาด N สมาชิกไม่ซ้ำ ผลรวม = SUM ค่าสูงสุด ≤ K คืน -1 ถ้าไม่ได้
ตัวอย่าง
N=4, SUM=16, K=9
ค่าต่ำสุดที่เป็นไปได้: 1+2+3+4 = 10
ค่าสูงสุดที่เป็นไปได้: 9+8+7+6 = 30
16 อยู่ในช่วง → มีคำตอบ
อาร์เรย์: [1, 2, 4, 9] (ผลรวม 16, max 9, ไม่ซ้ำ)
อัลกอริทึม (Greedy จากค่าสูงสุด)
- เริ่มจากอาร์เรย์ [0, 1, 2, ..., N] (index 0 ไม่ใช้)
- เดินจาก i=N ลง 1:
- ลองเพิ่มค่าที่ i เป็น K (สูงสุด)
- ถ้าผลรวมยัง < SUM → ยอมรับ, K--, อัปเดต sum
- ถ้าผลรวม ≥ SUM → ตั้งค่าให้พอดี SUM แล้ว break
โค้ด Python
def get_arr(N, SUM, K):
minimum_sum = (N * (N + 1)) // 2
maximum_sum = (N * K) - (N * (N - 1)) // 2
if minimum_sum > SUM or maximum_sum < SUM:
return -1
res = [i for i in range(N + 1)]
total = minimum_sum
i = N
while i >= 1:
x = total + (K - i)
if x < SUM:
total += (K - i)
res[i] = K
K -= 1
else:
res[i] += (SUM - total)
total = SUM
break
i -= 1
return res
N, SUM, K = 4, 16, 9
print(get_arr(N, SUM, K))
หมายเหตุ
โค้ดต้นฉบับใช้ / (float division) ควรใช้ // (integer division) ผลลัพธ์ต้นฉบับมี 4.0 แทน 4
ผลลัพธ์
[0, 1, 2, 4, 9]
