HDU/HDOJ----4302 Holedox Eating

多校第一场比较水的一道题，用线段树查找离要求点最近的目标。当时很快就有思路了，但是一直想拿ZKW版线段树写，由于没有完全掌握其精髓，当场没有做出来，赛后用常规版写的，而且写的比较丑陋……

#include <iostream>
#include <cstdio>
#include <cmath>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1^1
#define ll long long
#define N 100005
#define inf 1e9
#define linf 1e9
#define rinf -1
using namespace std;
struct node{
int left,right;
int num,lmost,rmost;
}seg[3*N];
int min(int a,int b) { return a<b?a:b; }
int max(int a,int b) { return a>b?a:b; }
void segtree_build(int l,int r,int rt){
//cout<<"<"<<l<<","<<r<<">"<<endl;
seg[rt].left=l,seg[rt].right=r;
seg[rt].num=0,seg[rt].lmost=linf,seg[rt].rmost=rinf;
if(l==r) return ;
int mid=(l+r)>>1;
segtree_build(lson);
segtree_build(rson);
}
node segtree_query(int L,int R,int l,int r,int rt){
node ans,tl,tr;
ans.lmost=linf,ans.rmost=rinf;
if(L<=l&&r<=R){
ans.lmost=min(ans.lmost,seg[rt].lmost);
ans.rmost=max(ans.rmost,seg[rt].rmost);
return ans;
}
int mid=(seg[rt].left+seg[rt].right)>>1;
if(L<=mid){
tl=segtree_query(L,R,lson);
ans.lmost=min(ans.lmost,tl.lmost);
ans.rmost=max(ans.rmost,tl.rmost);
}
if(R>mid){
tr=segtree_query(L,R,rson);
ans.lmost=min(ans.lmost,tr.lmost);
ans.rmost=max(ans.rmost,tr.rmost);
}
return ans;
}
void segtree_insert(int p,int rt,int index){
seg[rt].num+=index;
if(seg[rt].num==0) seg[rt].lmost=linf,seg[rt].rmost=rinf;
if(seg[rt].left==p&&seg[rt].right==p){
if(seg[rt].num) seg[rt].lmost=p,seg[rt].rmost=p;
return ;
}
int mid=(seg[rt].left+seg[rt].right)>>1;
if(p<=mid) segtree_insert(p,rt<<1,index);
else segtree_insert(p,rt<<1^1,index);
if(seg[rt].num){
seg[rt].lmost=min(seg[rt<<1].lmost,seg[rt<<1^1].lmost);
seg[rt].rmost=max(seg[rt<<1].rmost,seg[rt<<1^1].rmost);
}
}
void segtree_print(int L){
for(int i=1;i<=L*2;i*=2){
for(int j=0;j<i;j++){
int pos=i+j;
printf("<%d,%d> ",seg[pos].left,seg[pos].right);
if(seg[pos].lmost==linf) printf("no ");
else printf("%d ",seg[pos].lmost);
if(seg[pos].rmost==rinf) printf("no ");
else printf("%d ",seg[pos].rmost);
printf("%d| ",seg[pos].num);
}
printf("n");
for(int k=0;k<80;k++)
printf("-");
printf("n");
}
}
int main(){
//freopen("in.in","r",stdin);
int T,L,n,Case=1;
int lp,rp,ld,rd;
scanf("%d",&T);
while(T--){
scanf("%d%d",&L,&n);
segtree_build(0,L,1);
//segtree_print(L);
//cout<<"segtree_build done!"<<endl;
int lst=0,pos=0,ope,p;
ll ans=0;
while(n--){
scanf("%d",&ope);
if(ope){
lp=segtree_query(0,pos,0,L,1).rmost; ld=(lp==rinf?inf:abs(lp-pos)); //if(lp==inf) cout<<"no"<<' '; else cout<<"lp="<<lp<<' ';
rp=segtree_query(pos,L,0,L,1).lmost; rd=(rp==linf?inf:abs(rp-pos)); //if(rp==inf) cout<<"no"<<endl; else cout<<"rp="<<rp<<endl;
if(ld==inf&&rd==inf) continue;
else if(ld<rd||(ld==rd&&lst==-1)){
pos=lp,lst=-1,ans+=(ll)ld;
segtree_insert(pos,1,-1);
//segtree_print(L);
//cout<<"delete "<<pos<<" done!"<<endl;
}
else if(ld>rd||(ld==rd&&lst==1)){
pos=rp,lst=1,ans+=(ll)rd;
segtree_insert(pos,1,-1);
//segtree_print(L);
//cout<<"delete "<<pos<<" done!"<<endl;
}
else if(ld==rd&&lst==0){
segtree_insert(pos,1,-1);
//segtree_print(L);
//cout<<"delete "<<pos<<" done!"<<endl;
}
//cout<<"pos="<<pos<<' '<<"lst="<<lst<<' '<<"ans="<<ans<<endl;
}
else{
scanf("%d",&p);
segtree_insert(p,1,1);
//segtree_print(L);
//cout<<"insert "<<p<<" done!"<<endl;
}
}
printf("Case %d: %lldn",Case++,ans);
}
return 0;
}

最后

以上就是文艺机器猫为你收集整理的HDU/HDOJ----4302 Holedox Eating的全部内容，希望文章能够帮你解决HDU/HDOJ----4302 Holedox Eating所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。