HDU 5233 Gunner II (二分)"/>
HDU 5233 Gunner II (二分)
问题描述很久很久以前,有一个叫Jack的枪手。他非常喜欢打猎。一天,他去了一个小树林。那儿有n只鸟,还有n棵树。第i只鸟站在第i棵树的顶端。这些树从左到右排成一条直线。每一棵树都有它的高度。Jack站在最左边那棵树的左边。当Jack在高度为H的地方向右发射一棵子弹时,站在高度为H的树上且离Jack最近的鸟儿就会落下来。 Jack会射击多次,他想知道每次射击哪只鸟儿会落下来。输入描述
多组测试数据(大概5组),每一组的第一行给出n,m,n表示有n棵树和n只鸟,m表示Jack会射击m次。 在第二行,有n个整数h[1],h[2],h[3],…,h[n]表示这些树的高度。 在第三行,有m个整数,q[1],q[2],q[3],…,q[m]表示Jack射击的高度。[参数约定] 所有输入均为整数。 1<=n,m<=100000(10^5) 1<=h[i],q[i]<=1000000000(10^9)输出描述
对于每一个q[i],在一行中输出Jack射落的鸟的id。如果没有射中鸟儿,请输出-1。 (id 从1开始编号。)输入样例
5 5 1 2 3 4 1 1 3 1 4 2输出样例
1 3 5 4 2Hint
大数据输入,推荐使用快速读读入。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+100;struct node
{int index;int num;int book;
} a[maxn];bool cmp(node x,node y)
{if(x.num<y.num) return true;else if(x.num==y.num && x.index<y.index) return true;return false;
}int bsearch(int l,int r,int t)
{int mid;while(l<r) {mid=l+(r-l)/2;if(a[mid].num>t) r=mid;else if(a[mid].num<t) l=mid+1;else {if(a[mid].book==0) r=mid;else l=mid+1;}}return l;
}int main()
{int n,m,i,j,t;while(scanf("%d%d",&n,&m)!=EOF) {for(i=0;i<n;i++) {scanf("%d",&t);a[i].book=0;a[i].index=i;a[i].num=t;}sort(a,a+n,cmp);while(m--) {scanf("%d",&t);int ans=bsearch(0,n,t);if(a[ans].num==t && a[ans].book ==0) {a[ans].book =1;ans=a[ans].index+1;}else ans=-1;printf("%d\n",ans);}}return 0;
}
更多推荐
HDU 5233 Gunner II (二分)
发布评论