題意：有個公告板，大小為h*w,要貼n張公告，每個公告的長度是x，高度固定為1，公告放的要盡可能靠上并盡可能靠左，每給出一張公告，要求這個公告在滿足要求的情況下放在了第幾層。

Sample Input
3 5 5
2
4
3
3
3

Sample Output
1
2
1
3
-1

?

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <cmath> 6 # include <queue> 7 # define LL long long 8 using namespace std ; 9 10 const int maxn = 200010; 11 12 int MAX[maxn<<2] ; //結點開4倍 13 int h , w , n ; 14 15 void PushUP(int rt) //更新到父節點 16 { 17 MAX[rt] = max(MAX[rt * 2] , MAX[rt * 2 + 1] ); //rt 為當前結點 18 } 19 20 void build(int l , int r , int rt) //構建線段樹 21 { 22 MAX[rt] = w ; 23 if (l == r) 24 { 25 return ; 26 } 27 int m = (l + r) / 2 ; 28 build(l , m , rt * 2) ; 29 build(m + 1 , r , rt * 2 +1) ; 30 31 } 32 33 int query(int x , int l , int r , int rt) //區間求最大值的位子 直接把update的操作在query里做了 34 { 35 if (l == r) 36 { 37 MAX[rt] -= x ; 38 return l ; //每個葉子節點代表公告板的行 39 } 40 int m = (l + r) / 2 ; 41 int ret = 0 ; 42 if (MAX[rt * 2] >= x) 43 ret = query(x , l , m , rt * 2) ; 44 else 45 ret = query(x , m+1 , r , rt * 2 + 1) ; 46 PushUP(rt) ; 47 return ret ; 48 } 49 50 int main () 51 { 52 //freopen("in.txt","r",stdin) ; 53 while(scanf("%d %d %d" , &h , &w , &n) != EOF) // h為高 w為寬 n為數量 54 { 55 if (h > n) 56 h = n ; 57 build(1 , h , 1); 58 while (n--) 59 { 60 int x ; 61 scanf("%d" , &x) ; 62 if (x > MAX[1]) //如果一個公告的寬度 比1-h這區間 所有的剩余寬度都大 就是放不下了 63 printf("-1\n") ; 64 else 65 printf("%d\n" , query(x , 1 , h , 1)) ; 66 } 67 } 68 69 return 0 ; 70 } View Code

?

轉載于:https://www.cnblogs.com/mengchunchen/p/4603228.html

總結

以上是生活随笔為你收集整理的hdu 2795 公告板 （单点最值）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。