HDU 5233 Gunner II 离散化
2024-09-02 21:46:51
题目链接:
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
*/
最新文章
- RECONFIGURE语句会清空计划缓存么?
- box-sizing 属性、min-width属性、max-width属性
- 比较Windows Azure 网站(Web Sites), 云服务(Cloud Services)and 虚机(Virtual Machines)
- Linux内核循环链表经典分析和移植
- 【C语言】07-基本语句和运算
- 使用 rqt_console 和 roslaunch---8
- Operating Cisco Router
- C编译: makefile基础
- 图像采集系统的Camera Link标准接口设计
- 【视频编解码&#183;学习笔记】11. 提取SPS信息程序
- Lintcode223 Palindrome Linked List solution 题解
- ReentrantLock 与 AQS 源码分析
- git使用——推送本地文件到远程仓库
- Logcat
- Luogu 1086 - 花生采摘 - [简单模拟]
- 基于ROS和python,通过TCP通信协议,完成键盘无线控制移动机器人运动
- HTML CSS + DIV实现整体布局 part2
- 【总结整理】令人惊喜的app
- java生成pdf
- linux堆栈
热门文章
- PL/SQL 报错:动态执行表不可访问,本会话的自动统计被禁止。 在执行菜单里你可以禁止统计,或在v$session,v$sesstat 和vSstatname表里获得选择权限。
- Redis底层数据类型
- 第一篇随笔, 正在做 ESP32 , STM32 , 树莓派 RaspberryPi 的创客工具
- Go 学习之路:异常处理defer,panic,recover
- #define定义数据溢出的问题
- 证明SG中梯度的期望等于GD的梯度
- 20155207王雪纯 2006-2007-2 《Java程序设计》第二周学习总结
- 20155220 2016-2017-2《Java程序设计》课程总结
- Hello World 和 模块分解
- 20155339 2016-2017-2 《Java程序设计》第4周学习总结