UVA - 1372 Log Jumping

题意：给你n个长为k的横木，并给出左坐标，如果两个横木能都有重叠部分或临界的话，那么这两个横木就可以互相跳跃，问能形成多大的环

思路：排序后，假设当前的i是环里的，如果满足 x[i+1]-x[i-1]<=k && x[i+1]-x[i]<=k 的话，那么i+1块也可以加进环里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 6000;

int x[MAXN],k,n;

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&k);
        for (int i = 1; i <= n; i++)
            scanf("%d",&x[i]);
        sort(x+1,x+1+n);
        int i = 1;
        int ans = 0;
        while (i <= n){
            int pre = i;
            int cnt = 1;
            while (i < n && (cnt == 1 || x[i+1]-x[i-1] <= k) && x[i+1]-x[i] <= k)
                i++,cnt++;
            if (pre == i)
                i++;
            ans = max(ans,cnt);
        }
        printf("%d\n",ans);
    }
    return 0;
}

UVA - 1372 Log Jumping

原文：http://blog.csdn.net/u011345136/article/details/19021743