结题报告

0
11

题目:点此

单调队列思路:{

先读入,再排序,然后循环{

两个单调队列记端点,来一个数据,先维护,然后一边弹即将过时的数据,一边记录(万一这次是最优解,下次不是最优解(过时)),如果比最小值小就更新,最后进队。两单调队列同思路。

}

如果最小值没变就输出-1,否则输出最小值。

}

暴力思路:{

按x坐标排序,然后枚举左端点和右端点,如果不满足d的要求continue,否则判断是不是比最小值小,如果是就纪录,因为随着右端点的增加,宽度会不断的变长,不会是最小值了,如果比最小值大也是同理,所以都要退出循环。枚举完成后输出最小值。

}

犯的错误:{

1.有很多没用的代码。

2.记左端点和记右端点的许多判断条件是不一样的,我写成一样的了。

3.没有将不是最优解的数据弹出。

4.不能将判断数据是不是可行的If放在弹过时数据的while里。

5.应该一边弹一边更新最小值,而不是只记录。

6.不要的代码没删干净。

7.复制代码时没把要修改的地方改完。

8.想太多。

9.暴力枚举时应枚举第几滴水,而不是x坐标。

}

收获:{

1.把没用的代码去掉。

2.不要想当然。

3.要考虑周全。

4.不要的代码要删干净。

5.不要偷懒。

6.不要想太多。

7.即使是暴力也要考虑怎么优化。

}

单调队列代码:

 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 }

单调队列评测:

暴力代码:

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 struct drop{
 6     int x,y;
 7 }a[100000];
 8 bool cmp(drop c,drop d){
 9     return c.x<d.x;
10 }
11 int main(){
12     int n,d;
13     cin >> n >> d;
14     for(int i=0;i<n;i++){
15         cin >> a[i].x >> a[i].y;
16     }
17     sort(a,a+n,cmp);
18     int npos=a[n-1].x+1;
19     int min=npos;
20     for(int i=0;i<n;i++){
21         for(int j=i;j>=0;j--){
22             int w=a[i].x-a[j].x;
23             if(abs(a[i].y-a[j].y)<d){
24                 continue;
25             }
26             if(w<min){
27                 min=w;
28             }
29             break;
30         }
31     }
32     if(min==npos){
33         cout << -1;
34         return 0;
35     }
36     cout << min;
37     return 0;
38 }

View Code

暴力评测结果(网页URL已丢失,只剩我的截屏了):

<

发布回复

请输入评论!
请输入你的名字