题目链接:

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5233

bc(中文):http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=585&pid=1002

题解:

离散化之后,存在一张表里面(相同的值的id号用链表串起来,倒着存),每次查询完就把表首的删了,继续查。

之前离散的时候没有把查询的一起加进去,就一直t,估计是查询的时候很多是没有结果的,就会比较耗时间。改成一起哈希之后就过了。也没有做读写优化。

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
typedef long long LL; const int maxn=2e5+; struct Edge{
int v,ne;
Edge(int v,int ne):v(v),ne(ne){};
Edge(){};
}egs[maxn]; int n,m; int head[maxn],tot;
int ha[maxn];
int arr[maxn],q[maxn];
//将元素加入邻接表
void addEdge(int x,int id){
egs[tot]=Edge(id,head[x]);
head[x]=tot++;
}
//查询并删除
int queEdge(int x){
int p=head[x];
if(p==-) return -;
int ret=egs[p].v;
head[x]=egs[p].ne;
return ret;
}
/*
離散化去重
void get_ID(){
sort(ha,ha+n+m); ha[n+m]=ha[n+m-1]-1;
int cur=0;
for(int i=0;i<n+m;i++){
if(ha[i]!=ha[i+1]){
ha[cur++]=ha[i];
}
}
ha[n+m]=cur;
*/ //二分
int find(int x){
int lef=,rig=ha[n+m];
int ret=-;
while(lef<rig){
int mid=lef+(rig-lef)/;
if(ha[mid]<x){
lef=mid+;
}else if(ha[mid]>x){
rig=mid;
}else{
ret=mid;
break;
}
}
return ret;
} void init(){
memset(head,-,sizeof(head));
tot=;
} int main(){
while(scanf("%d%d",&n,&m)==&&n){
init();
//将输入的数和查询的数一起做离散化
for(int i=;i<n;i++){
scanf("%d",arr+i);
ha[i]=arr[i];
}
for(int i=;i<m;i++){
scanf("%d",q+i);
ha[n+i]=q[i];
}
//离散化
sort(ha,ha+n+m);
ha[n+m]=unique(ha,ha+n+m)-ha; //倒着插入,这样只要每次删除表首的数就可以了
for(int i=n-;i>=;i--){
int x=find(arr[i]);
addEdge(x,i);
}
for(int i=;i<m;i++){
int x=find(q[i]);
printf("%d\n",queEdge(x)+);
}
}
return ;
} /*
5 5
1 2 3 4 1
1 3 1 4 9
*/

最新文章

  1. RECONFIGURE语句会清空计划缓存么?
  2. box-sizing 属性、min-width属性、max-width属性
  3. 比较Windows Azure 网站(Web Sites), 云服务(Cloud Services)and 虚机(Virtual Machines)
  4. Linux内核循环链表经典分析和移植
  5. 【C语言】07-基本语句和运算
  6. 使用 rqt_console 和 roslaunch---8
  7. Operating Cisco Router
  8. C编译: makefile基础
  9. 图像采集系统的Camera Link标准接口设计
  10. 【视频编解码&#183;学习笔记】11. 提取SPS信息程序
  11. Lintcode223 Palindrome Linked List solution 题解
  12. ReentrantLock 与 AQS 源码分析
  13. git使用——推送本地文件到远程仓库
  14. Logcat
  15. Luogu 1086 - 花生采摘 - [简单模拟]
  16. 基于ROS和python,通过TCP通信协议,完成键盘无线控制移动机器人运动
  17. HTML CSS + DIV实现整体布局 part2
  18. 【总结整理】令人惊喜的app
  19. java生成pdf
  20. linux堆栈

热门文章

  1. PL/SQL 报错:动态执行表不可访问,本会话的自动统计被禁止。 在执行菜单里你可以禁止统计,或在v$session,v$sesstat 和vSstatname表里获得选择权限。
  2. Redis底层数据类型
  3. 第一篇随笔, 正在做 ESP32 , STM32 , 树莓派 RaspberryPi 的创客工具
  4. Go 学习之路:异常处理defer,panic,recover
  5. #define定义数据溢出的问题
  6. 证明SG中梯度的期望等于GD的梯度
  7. 20155207王雪纯 2006-2007-2 《Java程序设计》第二周学习总结
  8. 20155220 2016-2017-2《Java程序设计》课程总结
  9. Hello World 和 模块分解
  10. 20155339 2016-2017-2 《Java程序设计》第4周学习总结