FZU2136--取糖果 (线段树+RMQ) - c++编程基础

TOP

FZU2136--取糖果 (线段树+RMQ)

2015-11-21 01:04:06 来源: 作者: 【大中小】浏览:2次

Problem Description

有N个袋子放成一排，每个袋子里有一定数量的糖果，lzs会随机选择连续的几个袋子，然后拿走这些袋子中包含最多糖果的袋子。现问你，在选择x个袋子的情况下，lzs最坏情况下，也就是最少会拿到多少个糖果？对于x取值为1到n都分别输出答案。
Input

第一行一个整数T，表示有T组数据。

每组数据先输入一行一个整数N(1<=N<=100000)，表示袋子数，接下来一行输入N个正整数，输入的第i个数表示第i个袋子所装的糖果数。
Output

每组数据输出n行，第i行表示lzs随机取连续的i个袋子时的最坏情况下能拿到的糖果数。
Sample Input
1
5
1 3 2 4 5
Sample Output
1
3
3
4
5

我是先用rmq预处理区间最大值
然后枚举每个袋子,往左往右二分得到一个最大的区间,此区间的最大值就是枚举的袋子上的值,然后说明长度为1 -> R-L+1的区间都可以得到这个值,用线段树去维护最小值就行了

/*************************************************************************
    > File Name: FZU2136.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年04月23日 星期四 18时24分43秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; static const int N = 101010; int dp[N][20]; int LOG[N]; int arr[N]; struct node { int l, r; int add; int val; }tree[N << 2]; void initRMQ(int n) { for (int i = 1; i <= n; ++i) { dp[i][0] = arr[i]; } for (int j = 1; j <= LOG[n]; ++j) { for (int i = 1; i + (1 << j) - 1 <= n; ++i) { dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } } } int ST(int l, int r) { int k = LOG[r - l + 1]; return max(dp[l][k], dp[r - (1 << k) + 1][k]); } void build(int p, int l, int r) { tree[p].l = l; tree[p].r = r; tree[p].add = -1; if (l == r) { tree[p].val = inf; return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); tree[p].val = inf; } void pushdown(int p) { if (tree[p].add != -1) { if (tree[p << 1].add == -1) { tree[p << 1].add = tree[p].add; } else { tree[p << 1].add = min(tree[p].add, tree[p << 1].add); } if (tree[p << 1 | 1].add == -1) { tree[p << 1 | 1].add = tree[p].add; } else { tree[p << 1 | 1].add = min(tree[p].add, tree[p << 1 | 1].add); } tree[p << 1].val = min(tree[p].add, tree[p << 1].val); tree[p << 1 | 1].val = min(tree[p].add, tree[p << 1 | 1].val); tree[p].add = -1; } } void update(int p, int l, int r, int val) { if (l == tree[p].l && r == tree[p].r) { tree[p].val = min(val, tree[p].val); if (tree[p].add == -1) { tree[p].add = val; } else { tree[p].add = min(tree[p].add, val); } return; } pushdown(p); int mid = (tree[p].l + tree[p].r) >> 1; if (r <= mid) { update(p << 1, l, r, val); } else if (l > mid) { update(p << 1 | 1, l, r, val); } else { update(p << 1, l, mid, val); update(p << 1 | 1, mid + 1, r, val); } tree[p].val = min(tree[p << 1].val, tree[p << 1 | 1].val); } int query(int p, int pos) { if (tree[p].l == tree[p].r) { return tree[p].val; } pushdown(p); int mid = (tree[p].l + tree[p].r) >> 1; if (pos <= mid) { return query(p << 1, pos); } else { return query(p << 1 | 1, pos); } } int main() { int t; scanf("%d", &t); LOG[0] = -1; for (int i = 1; i <= 100000; ++i) { LOG[i] = (i & (i - 1)) ? LOG[i - 1] : LOG[i - 1] + 1; } while (t--) { int n; scanf("%d", &n); build(1, 1, n); for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); } initRMQ(n); for (int i = 1; i <= n; ++i) { int l = 1, r = i, mid; int L, R; L = R = i; while (l <= r) { mid = (l + r) >> 1; int maxs = ST(mid, i); if (maxs <= arr[i]) { L = mid; r = mid - 1; } else { l = mid + 1; } } l = i, r = n, mid; while (l <= r) { mid = (l + r) >> 1; int maxs = ST(i, mid); if (maxs <= arr[i]) { R = mid; l = mid + 1; } else { r = mid - 1; } } update(1, 1, R - L + 1, arr[i]); } for (int i = 1; i <= n; ++i) { printf("%d\n", query(1, i)); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu1251 字典树的应用（查询公共..	下一篇：[Practical.Vim(2012.9)].Drew.Ne..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: