这题是一题对线段树模板的调用...在省赛的时候出过一题类似的题目,叫bililili来着,和这题有异曲同工之妙.网址:acm.fafu.edu.cn..题目号多少忘记了;
这题的数据咋一看h,w是10^9,然后一定义,数组太大了怎么办!!!仔细看题目...最多就n个对不对,所以最多建n个节点(底层),多余的没有用..吓住我了!!
还有就是自己粗心问题吧...把h写成n,应该说算习惯吧...导致一直re,就是h<n的时候...
忘记说解法了...
解题方法:没必要用struct,用普通数组就好了..把每条的宽度定下来,用数组存起来,初始化为w;
父节点用来保存子节点的最大值,然后每次优先向左找,因为采用的是递归方式->深度优先搜索,一定是先往节点对应下标小的找..最上的问题解决了..
因为这题不用输出具体位置..所以最左问题没有必要解决..只需要每次找到的时候讲节点值减掉 广告需要占用的长度就行了..毕竟高就1,比较简单.
找到节点后记得更新..就这样..
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 using namespace std; 5 #define maxn 200050 6 #define max(a,b) a>b?a:b 7 int segment[maxn*4]; 8 int h,w,n; 9 void buildTree(int left,int right,int rt) 10 { 11 segment[rt] = w; 12 if(left == right) 13 return ; 14 int mid = (left + right) >> 1; 15 buildTree(left,mid,rt<<1); 16 buildTree(mid+1,right,rt<<1|1); 17 } 18 void update(int rt) 19 { 20 segment[rt] = max(segment[rt<<1],segment[rt<<1|1]); 21 } 22 int query(int left,int right,int rt,int value) 23 { 24 if(left == right) 25 { 26 segment[rt] -= value; 27 return left ; 28 } 29 int mid = (left + right) >> 1; 30 int res; 31 if(segment[rt<<1] >= value) 32 res =query(left,mid,rt<<1,value); 33 34 else 35 res = query(mid+1,right,rt<<1|1,value); 36 update(rt); 37 return res; 38 } 39 int main() 40 { 41 int value ; 42 while(~scanf("%d %d %d",&h,&w,&n)) 43 { 44 if(h>n) 45 h = n; //重要!!!!!最多就n行,没仔细看题目被10^9吓住了.. 46 buildTree(1,h,1); 47 while(n--) 48 { 49 scanf("%d",&value); 50 if(segment[1] < value) 51 puts("-1"); 52 else 53 printf("%d ",query(1,h,1,value));//习惯了,把h写成n!!一直re; 54 } 55 56 } 57 return 0; 58 }