首页 > 代码库 > hdu3193(RMQ)
hdu3193(RMQ)
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3193
转换成求价格在0到p的酒店中的最短距离。。。
p最大10000
当p为0时一定选
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const int maxn=10010; 7 struct node 8 { 9 int p,d; 10 bool operator< (const node&a) const { 11 if(p==a.p) return d<a.d; 12 return p<a.p; 13 } 14 }v[maxn],res[maxn]; 15 int a[maxn]; 16 int pmin[maxn][30]; 17 void RMQ_INIT() 18 { 19 int k=log(maxn+0.0)/log(2.0); 20 for(int i=0;i<=maxn;i++) pmin[i][0]=a[i]; 21 for(int j=1;j<=k;j++) 22 for(int i=0;i+(1<<j)-1<=maxn;i++) 23 pmin[i][j]=min(pmin[i][j-1],pmin[i+(1<<j-1)][j-1]); 24 } 25 int rmq(int x,int y) 26 { 27 int k=log(y*1.0-x+1)/log(2.0); 28 return min(pmin[x][k],pmin[y-(1<<k)+1][k]); 29 } 30 int main() 31 { 32 int n; 33 while(scanf("%d",&n)!=EOF) 34 { 35 int cnt=0; 36 for(int i=0;i<=maxn;i++) a[i]=0x3f3f3f3f; 37 for(int i=0;i<n;i++) 38 { 39 scanf("%d%d",&v[i].p,&v[i].d); 40 a[v[i].p]=min(a[v[i].p],v[i].d); 41 } 42 RMQ_INIT(); 43 for(int i=0;i<n;i++) 44 { 45 if(v[i].p==0) res[cnt++]=v[i]; //至少价格不会有更低的,选中 46 else{ 47 int d=rmq(0,v[i].p-1); 48 if(d>=v[i].d) res[cnt++]=v[i]; //如果比它便宜的酒店中最短距离不比它小,选中 49 } 50 } 51 sort(res,res+cnt); 52 printf("%d\n",cnt); 53 for(int i=0;i<cnt;i++) 54 printf("%d %d\n",res[i].p,res[i].d); 55 } 56 }
hdu3193(RMQ)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。