สมมติว่าเรามีตัวเลขสองตัว a และ b เพื่อนสองคนอยู่ที่ตำแหน่ง x =a และ x =b บนแกน OX เพื่อนแต่ละคนสามารถเคลื่อนที่ไปทีละเส้นในทิศทางใดก็ได้ไม่จำกัดจำนวนครั้ง โดยการเคลื่อนไหว ความเหนื่อยล้าของเพื่อนจะเปลี่ยนไปตามกฎต่อไปนี้ ท่าแรกเพิ่มความเหนื่อยล้า 1 ท่า ท่าที่สองเพิ่มความเหนื่อยล้า 2 ต่อไปเรื่อยๆ สองคนต้องการพบจุดจำนวนเต็มหนึ่งจุดบนแกน OX เราต้องหาค่าความเหนื่อยล้าขั้นต่ำที่ควรได้รับ
ดังนั้นหากอินพุตเป็นเหมือน a =5; b =10 จากนั้นผลลัพธ์จะเป็น 9 เนื่องจากวิธีที่เหมาะสมวิธีหนึ่งมีดังต่อไปนี้ เพื่อนคนแรกควรขยับไปทางขวา 3 ก้าว และเพื่อนคนที่สองก้าวไปทางซ้าย 2 ก้าว ดังนั้น ความเหนื่อยล้าทั้งหมดจึงกลายเป็น 1 + 2 + 3 + 1 + 2 =9.
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ans := |a - b| sum := ans / 2 return (sum + (ans mod 2)) * (sum + 1)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b){
int ans = abs(a - b);
int sum = ans / 2;
return (sum + (ans % 2)) * (sum + 1);
}
int main(){
int a = 5;
int b = 10;
cout << solve(a, b) << endl;
} อินพุต
5, 10
ผลลัพธ์
9
