UVa 1372 - Log Jumping

#贪心
Published on 2016-10-25

题目地址

描述

有 n(n≤5000)n(n\le 5000) 根木棍，长度均为 k(1≤k≤105)k(1\le k\le {10}^5)，左端点的坐标为 xi(−106≤xi≤106)x_i(-{10}^6\le x_i\le {10}^6)，如果两根木棍 ii 和 jj 满足 ∣xi−xj∣≤k\vert x_i - x_j\vert \le k，那就可以从 ii 跳到 jj（或相反）。你可以从任何一根木棍开始跳，经过其他木棍至多一次，最终回到起跳的木棍，问最多能经过多少个木棍？

分析

我们先将木棍按 xix_i 从小到大排序，不难发现，一定存在一个最优解，使得经过的木棍 对 1≤i≤m1\le i \le m 有 pi=pi−1+1p_i = p_{i - 1} + 1（通俗的说就是都相邻）。

这样我们对每一个 ii，考虑以 ii 为最左的木棍的答案：首先判断 ii 与 i+1i + 1 是否相交，如果相交，那么就可以构成一个长度为 22 的环。接着从 i+2i + 2 开始，顺序考虑能不能加入位置 j,i+2≤j<nj, i + 2\le j <n，对于 jj，考虑 jj 能不能与 j−1j - 1 和 j−2j - 2 都相交，如果不可以都相交，那么永远没办法扩大环，更新答案 j−ij - i。否则我们考虑在跳向 j−1j - 1 的时候跳向 jj，然后从 jj 跳回 j−1j - 1，这样就让环增大了 11。
这样做复杂度是 O(n2)O(n^2) 的。

一个优化是如果 ii 在 jj 处失败，那么下一次就可以从 max(i+1,j−1)\max(i + 1, j - 1) 处开始，因为在 jj 处失败意味着 jj 与 j−2j - 2 不相交（也有可能是 j−1j - 1 就是起点，jj 与 j−1j - 1 不相交，这也就是要试一下 i+1i + 1 的原因，我们假设没发生这种情况），如果从 i+1i + 1 处开始，那么到 jj 时还是不与 j−2j - 2 相交，答案不更大。而 j−1j - 1 与 jj 是有可能相交的，所以我们要从 j−1j - 1 开始。
这样的话每个点最多被访问 3 次，复杂度降为了 O(n)O(n)。

代码

//  Created by Sengxian on 2016/10/25.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 1372 贪心 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int MAX_N = 5000 + 3;
int n, L, x[MAX_N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    int caseNum = ReadInt();
    while (caseNum--) {
        n = ReadInt(), L = ReadInt();
        for (int i = 0; i < n; ++i) x[i] = ReadInt();
        sort(x, x + n);
        int ans = 1;
        for (int i = 0, j = 0; i + 1 < n; i = max(i + 1, j - 1)) {
            #define check(i, j) (x[j] - x[i] <= L)
            if (check(i, i + 1)) j = i + 2;
            else continue;
            while (j < n && check(j - 1, j) && check(j - 2, j)) ++j;
            ans = max(ans, j - i);
        }
        printf("%d\n", ans);
    }
    return 0;
}
UVa 10271 - Chopsticks