题解】 HDU 5199 Gunner"/>
【题解】 HDU 5199 Gunner
目录
题目描述
题意分析
AC代码
题目描述
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Long long ago, there is 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 bird which stands in the tree with height H will falls.
Jack will shot many times, he wants to know how many birds fall during each shot.
a bullet can hit many birds, as long as they stand on the top of the tree with height of H.
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]
1≤n,m≤1000000(106)
1≤h[i],q[i]≤1000000000(109)
All inputs are integers.
Output
For each q[i], output an integer in a single line indicates the number of birds Jack shot down.
Sample Input
4 3
1 2 3 4
1 1 4
Sample Output
1
0
1
题意分析
题意:N棵 高H 的树顶上有一只鸟 ,这个猎人接下来会发射 M次 高为H的子弹。扫到了,鸟儿就die了
问你每次打落几只鸟。数据十分大,用CIN会直接TE掉。MAP内自建一颗红黑树,速度还是很快的
AC代码
#include <iostream>
#include <map>
#define MAXN 1000005
using namespace std;map <long long,long long> s;int main()
{long long n,m,i,p;while(~scanf("%lld%lld",&n,&m)){s.clear();for(i=0;i<n;i++){scanf("%lld",&p);s[p]++;}for(i=0;i<m;i++){scanf("%lld",&p);printf("%lld",s[p]);if(s[p]>0){s[p]=0;}printf("\n");}}return 0;
}
更多推荐
【题解】 HDU 5199 Gunner
发布评论