水题（Checkpoints，cf 709B）

62 阅读 0 评论 41 点赞

我是靠谱客的博主朴实天空，最近开发中收集的这篇文章主要介绍水题（Checkpoints，cf 709B），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在数轴上，给出n个点的坐标和你现在的坐标。输出最少的行走距离，使你访问至少n-1个点。

其实就是选一个点不访问，这个点选最左或最右即可。

可以先往左走，再往右走。

或者先往右走，再往左走。

1个点直接输出0。

一开始分了9类在那讨论来讨论去的，最后还错了。

可能是我觉得分得详细，每一类就相对简单，不容易错，而且每一类都保证不重不漏。

但是有时候，真的，有些情况你忽视掉了，怎么分你都还是会遗漏。（类是没分错，但有一些细小的东西是与如何分类无关的）

而且9类讨论起来十分麻烦，花去了你大量精力，却收效甚微。（依然无法发现那些细小的东西）

事实上如果可以分成一个或几个大类+一个或几个特例便是最好。但一定要证明不重不漏。毕竟不如分成9类那么有逻辑。很容易在分类上出错。

省下的时间和精力可以多去想想有没有什么情况被你忽视掉了。

我说的细小的东西大概是指你最小的类中的任何情况。

其实也不能一概而论，只能说在这题中，分九类不值。

我遗漏的情况是：

当选择不去最左边的点时，只考虑了先左后右。

当选择不去最右边的点时，只考虑了先右后左。

然后，尽量不要写一长串式子，不方便检查，也容易错。如：

printf("%dn",min(min(abs(a-l2),abs(a-r1))+abs(r1-l2),min(abs(a-l1),abs(a-r2))+abs(l1-r2)));

写成这样岂不更好？

int ans1=min(abs(a-l2),abs(a-r1))+abs(r1-l2);
int ans2=min(abs(a-l1),abs(a-r2))+abs(l1-r2);
printf("%dn",min(ans1,ans2));

AC代码

分九类

<pre name="code" class="cpp">#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,a;
    scanf("%d %d",&n,&a);
    vector<int>l;
    vector<int>r;
    int temp;
    while(n--)
    {
        scanf("%d",&temp);
        if(temp<a) l.push_back(temp);
        if(temp>a) r.push_back(temp);
    }
    sort(l.begin(),l.end());
    sort(r.begin(),r.end());
    if(l.size()==0)
    {
        if(r.size()==0) puts("0");
        else if(r.size()==1) puts("0");
        else printf("%dn",r[r.size()-2]-a);
    }
    else if(l.size()==1)
    {
        if(r.size()==0) puts("0");
        else if(r.size()==1) printf("%dn",min(r[0]-a,a-l[0]));
        else printf("%dn",min(min(r[r.size()-1]-a,a-l[0]+r[r.size()-2]-l[0]),r[r.size()-2]-a+r[r.size()-2]-l[0]));
    }
    else
    {
        if(r.size()==0) printf("%dn",a-l[1]);
        else if(r.size()==1) printf("%dn",min(min(a-l[0],r[0]-a+r[0]-l[1]),a-l[1]+r[0]-l[1]));
        else printf("%dn",min(min(a-l[0]+r[r.size()-2]-l[0],r[r.size()-1]-a+r[r.size()-1]-l[1]),min(r[r.size()-2]-a+r[r.size()-2]-l[0],a-l[1]+r[r.size()-1]-l[1])));
    }
    return 0;
}

一个大类+一个特例

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,a;
    scanf("%d %d",&n,&a);
    vector<int>pt;
    int temp;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        pt.push_back(temp);
    }
    sort(pt.begin(),pt.end());
    if(n==1) puts("0");
    else
    {
        int l1=pt[0];
        int l2=pt[1];
        int r1=pt[pt.size()-1];
        int r2=pt[pt.size()-2];
        printf("%dn",min(min(abs(a-l2),abs(a-r1))+abs(r1-l2),min(abs(a-l1),abs(a-r2))+abs(l1-r2)));
    }
    return 0;
}