结题报告

2020-01-30 16:00:49来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

结题报告

题目:点此

思路:{

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

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

}

如果最小值没变就输出-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 }

评测:


原文链接:https://www.cnblogs.com/eason66-blog/p/P2698-USACO12MARFlowerPot.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:二叉树--普通二叉树的创建和遍历

下一篇:动态规划:最大子串和