題目：點此 思路：{ 先讀入，再排序，然後迴圈{ 兩個單調隊列記端點，來一個數據，先維護，然後一邊彈即將過時的數據，一邊記錄（萬一這次是最優解，下次不是最優解（過時）），如果比最小值小就更新，最後進隊。兩單調隊列同思路。 } 如果最小值沒變就輸出-1，否則輸出最小值。 } 犯的錯誤：{ 1.有很多沒 ...
題目：點此
思路：{
先讀入，再排序，然後迴圈{
兩個單調隊列記端點，來一個數據，先維護，然後一邊彈即將過時的數據，一邊記錄（萬一這次是最優解，下次不是最優解（過時）），如果比最小值小就更新，最後進隊。兩單調隊列同思路。
}
如果最小值沒變就輸出-1，否則輸出最小值。
}
犯的錯誤：{
1.有很多沒用的代碼。
2.記左端點和記右端點的許多判斷條件是不一樣的，我寫成一樣的了。
3.沒有將不是最優解的數據彈出。
4.不能將判斷數據是不是可行的If放在彈過時數據的while里。
5.應該一邊彈一邊更新最小值，而不是只記錄。
6.不要的代碼沒刪乾凈。
7.複製代碼時沒把要修改的地方改完。
8.想太多。
}
收穫：{
1.把沒用的代碼去掉。
2.不要想當然。
3.要考慮周全。
4.不要的代碼要刪乾凈。
5.不要偷懶。
6.不要想太多。
}
代碼：
1 #include <iostream> 2 #include <algorithm> 3 #include <deque> 4 #include <cmath> 5 #include <cstdio> 6 using namespace std; 7 struct drop{ 8 int x,y; 9 }a[100000]; 10 bool cmp(drop c,drop d){ 11 return c.x<d.x; 12 } 13 deque <int> maxz,minz; 14 int main(){ 15 int wl,ans=2147483645; 16 int n,d; 17 cin >> n >> d; 18 for(int i=0;i<n;i++){ 19 scanf("%d %d",&a[i].x,&a[i].y); 20 } 21 sort(a,a+n,cmp); 22 int npos=ans; 23 wl=npos+1; 24 for(int i=0;i<n;i++){ 25 int old; 26 while(!maxz.empty()&&a[maxz.back()].y<a[i].y){ 27 maxz.pop_back(); 28 } 29 while(!maxz.empty()&&a[maxz.front()].y-a[i].y>=d){ 30 old=maxz.front(); 31 maxz.pop_front(); 32 wl=a[i].x-a[old].x; 33 if(ans>wl){ 34 ans=wl; 35 } 36 } 37 maxz.push_back(i); 38 while(!minz.empty()&&a[minz.back()].y>a[i].y){ 39 minz.pop_back(); 40 } 41 old=minz.front(); 42 while(!minz.empty()&&a[i].y-a[minz.front()].y>=d){ 43 old=minz.front(); 44 minz.pop_front(); 45 wl=a[i].x-a[old].x; 46 if(ans>wl){ 47 ans=wl; 48 } 49 } 50 minz.push_back(i); 51 } 52 if(ans==npos){ 53 cout << -1; 54 return 0; 55 } 56 cout << ans; 57 return 0; 58 }
評測：
