为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 274491
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 const int maxn=1000010;
 5 int n,k;
 6 deque<int>q;
 7 int num[maxn];
 8 bool is_greater(int a,int b)
 9 {
10     return a>b;
11 }
12 bool is_less(int a,int b)
13 {
14     return a<b;
15 }
16 void solve( bool (*is_better)(int ,int) )
17 {
18     q.clear();
19     for(int i=1;i<k;i++)
20     {
21         while(!q.empty() && (*is_better)(num[i],num[q.back()]))
22             q.pop_back();
23         q.push_back(i);
24     }
25     for(int i=k;i<=n;i++)
26     {
27         while(!q.empty() && (*is_better)(num[i],num[q.back()]))
28             q.pop_back();
29         while(!q.empty() && i-q.front()>=k)
30             q.pop_front();
31         q.push_back(i);
32         printf("%d",num[q.front()]);
33         if(i==n) printf("\n");
34         else printf(" ");
35     }
36 }
37 int main()
38 {
39     scanf("%d%d",&n,&k);
40     for(int i=1;i<=n;i++)
41         scanf("%d",&num[i]);
42     solve(is_less);
43     solve(is_greater);
44 }

posted on 2010-08-05 08:45 baby-fly 阅读(356) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理