正解：DP
比較好寫的/我用的演算法：貪心
首先需要理解幾個地方：
-
第二行輸入的 \(n\) 個數字是每盞燈所在的地方，可以不按順序，燈與燈之間的距離是個變數，
-
對于任意一段區間，只要是在 \(\text{dist}\) 的范圍內，可以關閉多盞燈，
貪心策略：首先排序，然后回圈 \(2\) ~ \(n-1\) ，因為第一盞和最后一盞不能關，若前后滿足條件，則將第 \(i\) 盞與第 \(i-1\) 盞互換，這樣覆寫了當前燈，也就相當于“關燈”，下一次比較時，相當于仍然在與第 \(i-1\) 盞燈比較（即可行區間，可以畫圖理解），若在某一時刻不符合條件，則自動比較另一組資料，按此方式處理，時間復雜度 \(O(n)\) ，可 \(\text{AC}\) ，
完整代碼如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,d,a[100001],ans;
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=2;i<n;i++){
if(a[i+1]-a[i-1]<=d){
a[i]=a[i-1];
ans++;
}
}
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63271.html
標籤：C++
上一篇：題解 P6013 【壓歲錢】