Gunner II（二分，map,数字转化）

时间：2022-12-09 03:35:18

Gunner II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1740    Accepted Submission(s): 635

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
Hint

Huge input, fast IO is recommended.

 

题解：这题就做的曲折了，刚开始一看不就是个hash表么，倒着记录下就好了，然而在tel和mel中，我放弃了。。。

于是就想着二分了，对于已经用过的怎么办，再开个数组记录已经用过的，可是数组太大了啊，于是我用map来记录，可是是数字啊，木事木事，转化成string不就好了。。。想用stl里的二分类，但是是结构体啊，那就自己写。。。

写完了，感觉很有可能wa，因为二分感觉写的有点挫，交了下竟然AC了。。。我只想笑。。

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<map>

#include<string>

using namespace std;

const int INF=0x3f3f3f3f;

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define P_ printf(" ")

#define mem(x,y) memset(x,y,sizeof(x))

const int MAXN=1e5+;

struct Node{

    int v,num;

    bool operator < (const Node &b) const{

        if(v!=b.v){

            return v<b.v;

        }

        else return num<b.num;

    }

};

Node dt[MAXN];

int main(){

    int n,m;

    while(~scanf("%d%d",&n,&m)){

        map<string,int>mp;

        for(int i=;i<=n;i++)SI(dt[i].v),dt[i].num=i;

        sort(dt+,dt+n+);

        int x;

        sort(dt+,dt+n+);

        for(int i=;i<m;i++){

            SI(x);

            char s[];

            itoa(x,s,);

            int l=,r=n+,mid;

            while(l<=r){

                mid=(l+r)>>;

                if(x<=dt[mid].v)r=mid-;

                else l=mid+;

            }

            if(dt[r++mp[s]].v==x){

                printf("%d\n",dt[r++mp[s]].num);

                mp[s]++;

            }

            else puts("-1");

        }

    }

    return ;

}

我的hash表，TLE了：（贡献了9次TLE，MLE）贴下吧

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int INF=0x3f3f3f3f;

 #define SI(x) scanf("%d",&x)

 #define PI(x) printf("%d",x)

 #define P_ printf(" ")

 #define mem(x,y) memset(x,y,sizeof(x))

 const int MAXN=;

 int tp;

 int hsh[MAXN],head[MAXN],pos[MAXN],nxt[MAXN];

 int ans[];

 int q[];

 void add(int p,int x){

     int i=x%MAXN;

     hsh[tp]=x;

     pos[tp]=p;

     nxt[tp]=head[i];

     head[i]=tp++;

 }

 int main(){

     int n,m;

     while(~scanf("%d%d",&n,&m)){

         int x;

         mem(head,-);tp=;

         mem(nxt,);mem(hsh,);

         for(int i=;i<=n;i++){

             scanf("%d",&x);add(i,x);

         }

         for(int i=;i<=m;i++)scanf("%d",&q[i]);

         for(int i=m;i>=;i--){

                 x=q[i];

             int flot=;

             for(int j=head[x%MAXN];j!=-;j=nxt[j]){

                 if(x==hsh[j]){

                     ans[i]=pos[j];

                     flot=;

                     hsh[j]=;break;

                 }

             }

             if(!flot)ans[i]=-;

         }

         for(int i=;i<=m;i++)printf("%d\n",ans[i]);

     }

     return ;

 }

相关文章