2018 ICPC Asia Nakhon Pathom Regional Contest 部分题解

Problem D
Bus Stop
Time Limit 1 sec

题目大意：给你n个点，代表一条街上房子的坐标，问你至少修多少个公交车站可以覆盖所有房子（公交车站最多可以覆盖左右10公里）
样例一解释：可以在2那建一个，然后在200那建一个
样例二解释：在20那建一个，在80和200那各建一个

思路分析：我们建公交车站的时候要尽量建在中间，就例如样例二中的10和30，但其实我们可以不用考虑那么麻烦，我们可以先标记第一个房子的位置，然后找和第一个房子距离<=20的房子，因为车站可以覆盖左右各10公里，如果建在中间的话就是20公里，例如样例二中的10和30，如果找到第一个和标记房子距离>20公里的房子的话就代表我们需要重新建一个车站了，然后让车站数目+1，然后重新标记这个新房子，以此类推。最后还有一点这个题n是可以为0的，即可以有0座房子，这样的话就不需要建车站了（因为这个特判的疏忽我们被罚时了一次）。

#include <bits/stdc++.h>

using namespace std;

int a[2000010];
int main()
{
    int i,t,n,sum,book;
    scanf("%d",&t);
    while(t--)
    {
        sum=1;//初始化车站数为1
        scanf("%d",&n);
        if(n==0)//特判0
            printf("0\n");
        else
        {
            for(i=0; i<n; i++)//存点
                scanf("%d",&a[i]);
            book=a[0];//先标记第一个房子
            for(i=1; i<n; i++)
                if(a[i]-book>20)//如果距离>20，即需要建一个新的车站了
                {
                    sum++;//车站数目+1
                    book=a[i];//重新标记这个新房子
                }
            printf("%d\n",sum);
        }
    }
    return 0;
}