hdu5233 Gunner II
2024-09-07 12:54:14
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.
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)
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.
The id starts from 1.
Sample Input
5 5
1 2 3 4 1
1 3 1 4 2
1 2 3 4 1
1 3 1 4 2
Sample Output
1
3
5
4
2
3
5
4
2
这道题因为删除方法不对,一直T,终于改用vis后,900多ms水过去了。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
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<b.num;
}
int q[100006];
int find(int x,int l,int r)
{
int mid,j;
while(l<=r)
{
mid=(l+r)/2;
if(a[mid].num==x)break;
if(a[mid].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<int,int>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;
}
最新文章
- Linux运维常用命令总结
- 前端打包/自动化构建工具:fis3
- cmd导入oracle数据
- vijos p1002 dp ***
- javaweb毕业设计
- 《C++Primer》复习——with C++11 [1]
- Web.config配置详解【转 】
- C# Windows - ListView
- Machine Learning for Developers
- OCP prepare 20140628
- php 分析
- highlight.js 代码高亮插件的使用
- UI—视图的生命周期
- 237. Delete Node in a Linked List(leetcode)
- 关于Scanner类
- dedecms mvc 开发
- laravel 5.6
- Html Agility Pack解析Html(C#爬虫利器)
- cloudstack的虚拟机arp -a时网关的mac地址 都是Incomplete
- CentOs6.5 安装rabbitmq(转)
热门文章
- 执行py文件需要可执行权限吗?
- python模块详解 | psutil
- stat filename
- QLibrary 加载动态库
- .NET 云原生架构师训练营(模块二 基础巩固 Scrum 团队)--学习笔记
- C# 合并和拆分PDF文件
- DSL是什么?Elasticsearch的Query DSL又是什么?
- 中间件:ElasticSearch组件RestHighLevelClient用法详解
- 解决安装mysql动态库libstdc++.so.6、libc.so.6版本过低问题
- https://nginx.org/en/docs/http/request_processing.html