文明距离（civil）

题目描述

你被一个一向箔打中了，现在你掉到了一个一维空间中，也就是一个数轴上。

在这个数轴上，每秒会在一段连续的区间上出现“文明”。而你在每一秒开始的时候，可以花费x的代价移动x的距离，其中x是任意非负实数。当你移动结束以后，若你离“文明”的距离为y，你就需要花费y的代价使用“大眼睛”来观测这个文明，不然你就要被黑暗森林攻击了。此处距离是指你到这段区间中任意一点的距离的最小值。

现在，你收到了一系列信息，表明每秒的文明出现位置以及你的初始位置，请你最小化你的代价来完成任务。

输入格式

第一行两个正整数n,x，分别表示总秒数以及你的初始位置。

接下来n行，第i+1行有两个正整数li,ri，表示第i秒的时候的文明出现的位置。

输出格式

输出一行，表示最小代价。

样例

样例输入

样例输出

数据范围与提示

对于20%的数据，n<=10，x,li,ri<=10；

对于50%的数据，n<=2000,x,li,ri<=10^9；

对于100%的数据，n<=5*10^5,x,li,ri<=10^9。

solution

orzxjq！！！！！

3分钟屠出我永远也做不出的题。

我们假设我们现在的最优取值区间[l,r]

新来的一段区间为[a,b]

如果abcd有交集，那么下一步的最优解区间就是交集。

否则下一步的最优解区间是两个区间中间的那一段。

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 500005

using namespace std;

int n,x,l[maxn],r[maxn];

long long ans;

int main()

{

    cin>>n>>x;

    int nl=x,nr=x;

    for(int i=;i<=n;i++){

        scanf("%d%d",&l[i],&r[i]);

        if(nr<l[i]){

            ans+=l[i]-nr;

            nl=nr;nr=l[i];

        }

        else if(nl>r[i]){

            ans+=nl-r[i];

            nr=nl;nl=r[i];

        }

        else {

            nl=max(nl,l[i]);nr=min(nr,r[i]);

        }

    }

    cout<<ans<<endl;

    return ;

}

巴特西

文明距离（civil）

文明距离（civil）

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

最新文章

热门文章