一：題目

設(shè) x

1
?
,x
2
?
,…,x
n
?
是實直線上的n個點。用固定長度的閉區(qū)間覆蓋這n個點，至少需要多少個這樣的固定長度閉區(qū)間？

輸入格式:
第1行有2個正整數(shù)n(n<50)和k，表示有n個點，且固定長度閉區(qū)間的長度為k。

接下來的1行中有n個整數(shù) a
i
?
(?2000<a
i
?
<2000) ，表示n個點在實直線上的坐標(biāo)(可能相同)。

輸出格式:
最少區(qū)間數(shù)。

輸入樣例:

7 3 1 2 3 4 5 -2 6

輸出樣例:

3

二：思路：

思路：
1.首先先排序
2.然后確定第一個元素為標(biāo)桿，讓后一個元素減去前一個元素，如果其大于等于k，那么
區(qū)間數(shù)加一，且標(biāo)桿更新為減去前一個元素使其大于等于k的元素；
3.但要對最后不滿足條件的元素單獨處理

三：上碼

/**思路：1.首先先排序2.然后確定第一個元素為標(biāo)桿，讓后一個元素減去前一個元素，如果其大于等于k，那么區(qū)間數(shù)加一，且標(biāo)桿更新為減去前一個元素使其大于等于k的元素；3.但要對最后不滿足條件的元素單獨處理 */#include<bits/stdc++.h> using namespace std;int main(){int N,k;vector<int> v;cin >> N >> k;for(int i = 0; i < N; i++){int nums;cin >> nums;v.push_back(nums);}sort(v.begin(),v.end());int temp = v[0];int count = 0;for(int i = 1; i < N; i++){if(v[i] - temp >= k){temp = v[i];count++;// cout << temp << "wyj";}if(v[N-1] - temp < k && i != N-1){ //這里是為了處理剩余的元素也得占一個區(qū)間但其不滿足上一個if條件 count++; //但如果是最后一個元素那就不用統(tǒng)計進(jìn)去了 break;} }//count++;cout << count;} //測試用例1 //7 3 //1 2 3 4 10 -2 20//測試用例2 //7 3 //1 2 3 4 5 -2 6

加油 寶！！！！！！！！！！！！！！！

總結(jié)

以上是生活随笔為你收集整理的7-6 区间覆盖 (10 分)(思路+详解)Come 宝!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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