2020-2021 ACM-ICPC, Asia Seoul Regional Contest G. Mobile Robot(思维)

传送门

题意：

给出 $n$ 个机器人的位置，要求移动这些机器人，使其满足第 $i$ 个机器人和第 $i+1$ 个机器人的距离刚好为 $d$。

求这些机器人中的最大移动距离的最小值。

题解：

先假设第一个机器人不动，那么可以求出其他机器人的移动距离。

设 $ma$ 为向左移动的最大距离，$mi$ 为向右移动的最大距离，$mi$为负数，那么当移动第一个机器人时，$ma$ 和 $mi$ 会发变化，如果第一个机器人向右移动，$ma$会减小，但$mi$的绝对值会变大，反之向左移动也一样。

所以最优解就是两个数的绝对值中间的数，即 $(ma+abs(mi))/2=(ma-mi)/2$​

代码：

#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=1e6+5;
const int inf=0x3f3f3f3f;
ll a[MAXN];
vector<ll> ans;
int main()
{
    int n;
    ll d;
    scanf("%d%lld", &n, &d);
    for (int i = 1; i <= n;i++){
        scanf("%lld", &a[i]);
    }
    ll now = a[1];
    for (int i = 1; i <= n;i++){
        ans.push_back(a[i] - now);
        now += d;
    }
    ll s1 = *max_element(ans.begin(), ans.end())-*min_element(ans.begin(),ans.end());
    ans.clear();
    now = a[1];
    for (int i = 1; i <= n; i++) {
        ans.push_back(a[i] - now);
        now -= d;
    }
    ll s2 = *max_element(ans.begin(), ans.end()) - *min_element(ans.begin(), ans.end());
    s1 = min(s1, s2);
    if(s1%2==0){
        printf("%lld.0", s1 / 2);
    } 
    else{
        printf("%lld.5", s1 / 2);
    }
}

最后

以上就是霸气灯泡为你收集整理的2020-2021 ACM-ICPC, Asia Seoul Regional Contest G. Mobile Robot(思维)的全部内容，希望文章能够帮你解决2020-2021 ACM-ICPC, Asia Seoul Regional Contest G. Mobile Robot(思维)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。