題目：

坐標軸上從左到右依次的點為a[0]、a[1]、a[2]……a[n-1]，設一根木棒的長度為L，求L最多能覆蓋坐標軸的幾個點？

思路：

這是一道簡單的數(shù)組題，

方法也很簡單：直接從左到右掃描，兩個指針i和j，i從位置0開始，j從位置1開始，如果a[j] - a[i] <= L（采用<=,是因為可能某個區(qū)間不能剛好等于L），則j++，并記錄中間經(jīng)過的點個數(shù)，如果a[j] - a[i] > L，則j--回退，覆蓋點個數(shù)-1，回到剛好滿足條件的時候，將滿足條件的最大值與所求最大值比較，然后i++,j++，直到求出最大的點個數(shù)（結(jié)果可能有多種情況，只取第一次滿足的情況）。

代碼：

#include<iostream> using namespace std;int maxCover(int a[],int n,int L){int i=0,j=1;int count=1,maxCount=1,start;while(i<n && j<n){while((j<n) && (a[j]-a[i]<=L)){j++;count++;}j--;if(maxCount<count){maxCount=count;start=i;}i++;j++;count--;}cout<<"Covered points: \n";for(int i=start;i<start+maxCount;i++)cout<<a[i]<<" ";cout<<endl;return maxCount; }int main() {// testint len;int L=8;int a[] = { 1, 3, 6, 8, 9,10, 11, 12, 13, 15, 16, 17, 18 };len=sizeof(a)/sizeof(a[0]);cout<<"max count: "<<maxCover(a,len,L)<<endl;;int b[] = { 1, 2, 3, 4, 5, 100, 1000 };len=sizeof(b)/sizeof(b[0]);cout<<"max count: "<<maxCover(b,len,L)<<endl;return 0; }

運行結(jié)果：

轉(zhuǎn)載于:https://www.cnblogs.com/AndyJee/p/4561217.html

總結(jié)

以上是生活随笔為你收集整理的（笔试题）最大覆盖点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。