FJUT-1370 记录一次解题过程

题目在福工院的1370

首先看题目，好家伙，全英文

那么大致的题意就是。有几个城市同在一条线上（相当于在x轴上），max i是第i个城市到其他所有城市的距离中的最大值，min i也就是所有中最小的。

再看输入

第一行输入一个n(2 ≤ n ≤ 10⁵)，代表城市数量。第二行有n个数：x₁, x₂, ..., x_n ( - 10⁹ ≤ x_i ≤ 10⁹)，代表每个城市的横坐标。

看一下输出

输出n行，每行输出两个数，代表第i个城市到其他所有城市的距离最小值min i、最大值max i。

那么，这道题是想干什么呢？

就是给你n个在x轴上的点，x坐标告诉你了，求每个点距离其他点的最小值与最大值。

读懂了题，那就比较好写了。

首先读入每个城市横坐标

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

    cin>>x[i];

}

然后接下来分别求出每个max、min就可以了

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

    int max=;

    int min=inf;

    for(j=; j<n; j++) {

        if(abs(x[i]-x[j])>max&&i!=j)

           max=abs(x[i]-x[j]);

        if(abs(x[i]-x[j])<min&&i!=j)

            min=abs(x[i]-x[j]);

    }

    cout<<min<<" "<<max<<endl;

}

inf在函数外定义为0x3f3f3f3f，代表无穷大。这里的思路就是：你要比每个点到其他点的距离，那就先定一个点，让这个点与其他的点比较，这就有了上面的内层for循环。

max初始值为0，min初始值无穷大，定的点初始为第一个点，把它与第二个点比较，那么距离为3，而这个3大于初始的max，那新的max就变成了3。3小于初始的min，拿新的min就为3。然后再拿定点和下一个点比较，距离为7，大于max，故新的max为7，不小于min，故min还是3。以此类推，最后这个定点距其他所有点的min就为3，max就为12。

然后我们就需要设置第二个点、第三个点······为定点来比较了，因此就有了外层的for循环。

上面的代码中，if判断里有i!=j，这是为了避免定点与定点相比，否则相比之后，得出距离为0，那么最后它的min值就会为0，是错的。

那么完整的代码奉上（由于用了for嵌套，怕卡时间，就取消了共用缓冲区，代码为 int main() { 下面的那两行）

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

int x[];

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie();

    int n,i,j;

    cin>>n;

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

        cin>>x[i];

    }

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

        int max=;

        int min=inf;

        for(j=; j<n; j++) {

            if(abs(x[i]-x[j])>max&&i!=j)

                max=abs(x[i]-x[j]);

            if(abs(x[i]-x[j])<min&&i!=j)

                min=abs(x[i]-x[j]);

        }

        cout<<min<<" "<<max<<endl;

    }

    return ;

}

如果你提交这段代码，那么恭喜您喜提一个wa，至于原因我还没找到。这又是一道英文题，无法找网上的代码来借鉴。于是没办法，只有再写咯。其实写这段找min、max前，我的第一个思路是，因为这几个点都是按坐标顺序排着的，那么只用在它的位置上花功夫不就ok了吗。但当时感觉两个for循环找更稳，就没有细想。

那么从位置上来，需要考虑的就是两个东西。

首先。第一个点，它的max值一定是和最后一个点的差，min值一定是和第二个点的差。最后一个点也是这样，max值是和第一个点的差，min值是和倒数第二个点的差。

其次。中间的点的min值，一定是和相邻的点的差，需要找的就是到底是左边还是右边。max值一定是和第一个点或最后一个点的差。

那么如何找到底是左边还是右边相邻点离中间点的距离更小？到底是第一个还是最后一个点离中间点距离更大？事实上，把要比较的两个值直接放入min() max()函数就ok啦。

cout<<x[]-x[]<<" "<<x[n-]-x[]<<endl;

for(i=; i<n-; i++)

    cout<<min(x[i]-x[i-],x[i+]-x[i])<<" "<<max(x[i]-x[],x[n-]-x[i])<<endl;

cout<<x[n-]-x[n-]<<" "<<x[n-]-x[]<<endl;

显而易见，第一个点和最后一个点单独拿出来手动输出，中间的点，直接比较就ok

完整代码

#include<bits/stdc++.h>

using namespace std;

int x[];

int main() {

    int n,i;

    cin>>n;

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

        cin>>x[i];

    cout<<x[]-x[]<<" "<<x[n-]-x[]<<endl;

    for(i=; i<n-; i++)

        cout<<min(x[i]-x[i-],x[i+]-x[i])<<" "<<max(x[i]-x[],x[n-]-x[i])<<endl;

    cout<<x[n-]-x[n-]<<" "<<x[n-]-x[]<<endl;

    return ;

}

ok ac

巴特西

FJUT-1370 记录一次解题过程

最新文章

热门文章