程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2795 Billboard(線段樹)

HDU 2795 Billboard(線段樹)

編輯:C++入門知識

HDU 2795 Billboard(線段樹)


題意: 原始序列全為w, 找到最左邊的>=a的位置, 將該位置的值減去a,答案為該位置, 如果找不到符合要求的位置, 輸出-1。

該題利用線段樹遞歸特點來求其最左邊的大於等於a的位置。

線段樹遞歸的特點是從祖先結點開始自頂向下遞歸,訪問各個元素的順序一定是從左到右, 並且在遞歸之後可以順便維護區間結點的值。

利用這個特點, 我們可以直接查詢到>=a的最左邊的位置。該元素變成v - a, 然後順便維護改變了的值。 所以該題就成了維護區間最大值的線段樹題目。

細節參見代碼:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 200010;
int T,n,w,h,a,m,maxv[maxn*4];
void push_up(int o) {
    maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
void build(int l, int r, int o) {
    int m = (l + r) >> 1;
    maxv[o] = w;
    if(l == r) return ;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
    push_up(o);
}
int query(int v, int l, int r, int o) {
    int m = (l + r) >> 1, ans = 0;
    if(l == r) {
        maxv[o] -= v; return l;
    }
    if(maxv[o<<1] >= v) ans = query(v, l, m, o<<1);
    else ans = query(v, m+1, r, o<<1|1);
    push_up(o);
    return ans;
}
int main() {
    while(~scanf("%d%d%d",&h,&w,&n)) {
        if(h > n) h = n;
        build(1, h, 1);
        for(int i=0;i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved