hdu5233 Gunner II - c++编程基础

TOP

hdu5233 Gunner II

2015-11-21 00:59:43 来源: 作者: 【大中小】浏览:1次

Problem Description Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top of the i-th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the nearest bird which stands in the tree with height H will falls.

Jack will shot many times, he wants to know which bird will fall during each shot.

Input There are multiple test cases (about 5), every case gives n, m in the first line, n indicates there are n trees and n birds, m means Jack will shot m times.

In the second line, there are n numbers h[1],h[2],h[3],…,h[n] which describes the height of the trees.

In the third line, there are m numbers q[1],q[2],q[3],…,q[m] which describes the height of the Jack’s shots.

Please process to the end of file.

[Technical Specification]

All input items are integers.

1<=n,m<=100000(10^5)

1<=h[i],q[i]<=1000000000(10^9)

Output For each q[i], output an integer in a single line indicates the id of bird Jack shots down. If Jack can’t shot any bird, just output -1.

The id starts from 1.

Sample Input

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

Sample Output

1
3
5
4
2
这道题因为删除方法不对，一直T,终于改用vis后，900多ms水过去了。。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             using namespace std; struct node{ int id,num; }a[100006]; int n,vis[100006]; bool cmp(node a,node b){ if(a.num==b.num)return a.id>b.id; return a.num
            
             x)r=mid-1; else l=mid+1; } j=mid; if(vis[j]==1){ j--; while(1){ if(vis[j]==0)break; j--; } return j; } else{ j++; while(1){ if(j>n || vis[j]==1 || a[j].num>x){ j--;break; } j++; } return j; } } int main() { int m,i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { map
             
              hash; hash.clear(); for(i=1;i<=n;i++){ vis[i]=0; scanf("%d",&a[i].num); a[i].id=i; hash[a[i].num]++; } sort(a+1,a+1+n,cmp); for(i=1;i<=m;i++){ scanf("%d",&q[i]); if(hash[q[i]]==0){ printf("-1\n");continue; } else{ hash[q[i]]--; j=find(q[i],1,n); vis[j]=1; printf("%d\n",a[j].id); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdoj1584 蜘蛛牌区间型DP	下一篇：Leetcode[15]-3Sum

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: