AcWing 4579. 相遇问题

这道题做个今天的结尾

比较简单

正在备战csp吗，正好刷一下

难度：简单

时/空限制：1s / 256MB

总通过数：1738

总尝试数：2584

来源： CSP-J 2022 模拟赛

原题链接

4579. 相遇问题 - AcWing题库

题目描述

一个无限长的楼梯上站着两个人，其中一个人在第 a 级台阶上，另一个人在第 b 级台阶上。

两个人都可以自由的上下移动，每人每次可以向上或向下移动一级台阶。

每个人的每次移动都要消耗体力，具体为：

对于同一个人来说，其第 11次移动消耗的体力为 1，第 2 次移动消耗的体力为 2，第 3 次移动消耗的体力为 3，以此类推。

例如，如果一个人先向上移动一级台阶，再向下移动一级台阶，最后再次向上移动一级台阶，那么他消耗的总体力值为 1+2+3=6。

两个人想要通过合理移动，使得他们能够在同一级台阶上相遇，并且相遇时，两人消耗的总体力值之和尽可能小。

请你计算，两人消耗的总体力值之和的最小可能值。

输入格式

第一行包含一个整数 a。

第二行包含一个整数 b。

输出格式

一个整数，表示两人消耗的总体力值之和的最小可能值。

数据范围

所有测试点满足，1≤a,b≤1000，a≠b。

输入样例1：

3
4

输出样例1：

1

样例1解释

在本样例中，让第一个人上一级台阶或第二个人下一级台阶均可，消耗总体力为 1。

输入样例2：

101
99

输出样例2：

2

样例2解释

在本样例中，让第一个人下一级台阶，同时让第二个人上一级台阶即可，消耗总体力为 1+1=2。

输入样例3：

5
10

输出样例3：

9

样例3解释

在本样例中，一种最佳方案为让第一个人上两级台阶，同时让第二个人下三级台阶，消耗总体力为 1+2+1+2+3=9。

要解决这个问题，我们需要让两个站在不同台阶上的人通过移动相遇，并且使他们消耗的总体力值之和最小。
首先分析问题的关键特点：
两人初始位置分别在第 a 级和第 b 级台阶
每次移动消耗的体力值等于移动次数（第 1 次 1 点，第 2 次 2 点，依此类推）
目标是找到最佳相遇点，使总消耗体力最小
解题思路
首先计算两人初始位置的距离 d = |a - b|
当 d = 1 时，只需其中一人移动 1 步，总消耗为 1
当 d > 1 时，最优策略是让两人向中间位置移动：
距离较近的人移动 k 步
距离较远的人移动 d-k 步
为使总消耗最小，应让两人的移动次数尽可能均衡

首先，我代码的思路是：
1.确保 a < b
2.当两人相邻时直接返回 1
3.计算中间点 c = (a+b)/2
4.计算 a 到 c-1 的体力消耗
5.计算 c+1 到 b 的体力消耗
6.输出总消耗

下面是我的代码

#include <bits/stdc++.h>
using namespace std;int main(){int a,b;cin>>a>>b;if(a>b){swap(a,b);}if(b-a==1){cout<<"1"<<endl;return 0;//特判}int s=0,c=(a+b)/2,ans=0;for(int i=a; i<=c-1; i++) ans++, s+=ans;ans=0;//清空for(int i=c+1; i<=b; i++) ans++, s+=ans;cout<<s;return 0;
}