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

HDU 2795 Billboard.(線段樹)

編輯:關於C語言

HDU 2795 Billboard.(線段樹)


題目連接:http://acm.hdu.edu.cn/showproblem.php?pid=2795


~~~~

開始學習數據結構,從簡單的開始吧,刷題累了就寫解題報告,哈哈,沸騰吧,Segment tree!

~~~~

大致題意:一塊 h*w的廣告牌,藍後就是n塊1*wi大小的廣告,依次貼到廣告牌上,而且總是貼到最左上角,問貼完所有廣告後所占的高度是多少?

#include
#include
#define lson rt<<1,s,mid
#define rson rt<<1|1,mid+1,e
using namespace std;

const int maxn=222222;
int tre[maxn<<2];
int h,w,n;

void pushup(int rt)
{
    tre[rt]=max(tre[rt<<1],tre[rt<<1|1]);
}

void build(int rt,int s,int e)
{
    tre[rt]=w;
    if(s==e)
        return ;
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}

int query(int rt,int s,int e,int x)
{
    if(s==e)
    {
        tre[rt]-=x;
        return s;
    }
    int mid=(s+e)>>1;
    int ans=(tre[rt<<1]>=x)?query(lson,x):query(rson,x);
    pushup(rt);     //直接把更新操作寫到query函數裡。
    return ans;
}

int main()
{
    while(scanf("%d%d%d",&h,&w,&n)==3)
    {
        if(h>n) h=n;    //h>n的話,多余的就空間就浪費掉了,而且貌似會RE
        build(1,1,h);
        while(n--)
        {
            int q;
            scanf("%d",&q);
            if(tre[1]

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