#每日一面BAT#第20题 绳子覆盖点


数轴上从左到右有n个点a[0],a[1]...a[n-1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。
已邀请:

cpcs - 诚实努力

赞同来自:


答案
O(n^2)枚举自然都能能想到。给个O(n)的想法。
以每个i为起点,只希望覆盖更多的点。
注意每次循环best和i都只增不减,尽管两个循环,复杂度还是O(n)的。
int calculate(int *a, int n, int L) {
  
   int best = 0;
    for (int i = 0; i + best < n; ++i) {
        for (; (i + best < n) && (a[i + best] - a[i] <= L); ++best)
        ;
    }
    return best;
}

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~