xth 砍樹

2019-11-06 06:10:40

字體：大中小

來源：轉載

供稿：網友

題目描述

在一個涼爽的夏夜，xth和rabbit來到花園里砍樹。為啥米要砍樹呢?是這樣滴，小菜兒的兒子窄森要出生了。xth這個做伯伯的自然要做點什么。于是他決定帶著rabbit去收集一些木材，給窄森做一個嬰兒車……( xth早就夢想著要天天打菜兒他兒窄森的小PP，到時候在嬰兒車里安裝一個電子遙控手臂，輕輕一按，啪啪啪……“烏卡卡一一”xth牙區惡滴笑了，“不要告訴rabbit，她會說我缺德的……”xth如是說)。花園里共有n棵樹。為了花園的整體形象，rabbit要求xth只能在m個區域砍伐，我們可以將這m個區域看成m個區間，樹的間距相等，都是1，我們將每個區間設為[x,y]。那么長度為k的區間中就有k棵樹。樹木的高度不等。現在xth想測量一下，每個區間樹木砍伐后所得的木材量是多少，而且每次測量后他都會砍下標號為(x+y)/2的那棵作為紀念。以方便他安排人手。(同一個區間的樹木可以重復砍伐，我們認為被砍過的樹木高度為0)每棵樹的木材量=樹的高度*3.14(注意是3.14不是π)。

輸入

第一行，一個整數n。第二行，共n個整數，表示每棵樹的高度。第三行，一個整數m，表示共m個區間。以下m行，每個區間[x, y]的左右端點x, y。

輸出

共m行，每行一個數，表示每個區間的木材量。結果精確到小數點后兩位。

樣例輸入

5 1 2 3 4 5 2 1 4 2 4

樣例輸出

31.40 21.98

提示

數據規模

對于30%的數據，有n ≤ 5000,m ≤ 5000; 對于100%的數據，有n ≤ 200000,m ≤ 200000;

樣例解釋

第一次砍[1,4] 的樹后，森林變為：1 0 3 4 5

分析

做題前先思考這道題水不水，再來做。O(∩_∩)O … —zjf

測試鏈接

首先這點題還是用樹狀數組。（~~怎么還是樹狀數組~~，(⊙﹏⊙)b）然后我們把常用的幾個函數加上。這點題其實有一個地方，如果稍微不仔細一點讀題，會死得很慘。等一下我們再來說這個坑的地方。

#include<cstdio>#define lowbit(x) (x&-x)int tree[200005],f[200005];void update(int pos,int val){ while(pos<=n){ tree[pos]+=val; pos+=lowbit(pos); } }int getsum(int x){ int sum=0; while(x>0){ sum+=tree[x]; x-=lowbit(x); } return sum;}

.

回去鏈接–>這里看到了吧，前面一切都很順利，因為坑的地方還沒有來，我們可以很輕松的碼下程序的主函數：

int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&f[i]); update(i,f[i]); } scanf("%d",&m); while(m--){ int x,y; scanf("%d%d",&x,&y); 坑點

讓我們來輕松（zuōsǐ）的來測一組數據。。。

5 1 1 1 1 1 3 1 5 2 4 3 3

然后呢……

（我寫成一行是為了好觀察輸出~~~）

答案是 15.70 6.28 -3.14

what，負數是什么意思？肯定是哪里錯了。。。請大家看到主函數第14行，直達–>這里

.

注意了：原題如下

花園里共有n棵樹。為了花園的整體形象，rabbit要求xth只能在m個區域砍伐，我們可以將這m個區域看成m個區間，樹的間距相等，都是1，我們將每個區間設為[x,y]。那么長度為k的區間中就有k棵樹。樹木的高度不等。現在xth想測量一下，每個區間樹木砍伐后所得的木材量是多少，而且每次測量后他都會砍下標號為(x+y)/2的那棵作為紀念。以方便他安排人手。(同一個區間的樹木可以重復砍伐，我們認為被砍過的樹木高度為0)每棵樹的木材量=樹的高度*3.14(注意是3.14不是π)。

沒有什么不對的呀。╮(╯_╰)╭ 在這里↓↓↓↓↓

同一個區間的樹木可以重復砍伐

O(∩_∩)O哈哈哈~，所以我們要把源程序修改一下，加上下面的第14行。if(getsum(p)-getsum(p-1))，其實這是判斷這個地方是否為0，然后在加減的。被坑了吧。。。我第一次也是因為這樣一分都沒有得到的。。。

int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&f[i]); update(i,f[i]); } scanf("%d",&m); while(m--){ int x,y; scanf("%d%d",&x,&y); printf("%.2lf/n",(getsum(y)-getsum(x-1))*3.14); int p=(x+y)/2; if(getsum(p)-getsum(p-1)) update(p,-f[p]); }}

下面是AC代碼。