首页 > 代码库 > HDU3193 Find the hotel

HDU3193 Find the hotel

题解:

将其中一边sort,然后另一边使用rmq_min.对于p[i],只要rmq_min(1,i-1)>=p[i].se即可

但是这有一个问题。忽略了sort的那条边相等的情况

这里提供2种处理方式

1.在判断p[i]时,添加一个判断

while(p[i].fs==p[k].fs&&k>=1)  k--;if(k==0) goal[tmp++]=p[i];

2.注意到题目有:The number will be non-negative and less than 10000.

所以可以初始化一个b[maxn]为极大值。然后b[p[i].fs]=p[i].se;

然后rmq(0,p[i].fs-1)即可

注意到是非负,可能为0,所以全部都加1,输出时全部都减一.

代码:

//第一种处理方式 #include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<map>#include<set>#include<vector>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define MS(x,y) memset(x,y,sizeof(x))#define MC(x,y) memcpy(x,y,sizeof(x))#define ls o<<1#define rs o<<1|1#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=10010;const int N=1e9;const int mod=1e9+7;ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}//-----------------------------------------------------------------------------P p[maxn],goal[maxn];int n,tmp;int mi[maxn][20];void rmq_init(){    for(int i=1;i<=n;i++) mi[i][0]=p[i].se;    int k=(int)(log(n*1.0)/log(2.0));    for(int i=1;i<=k;i++)    for(int j=1;j<=n;j++)    {        mi[j][i]=mi[j][i-1];        if(j+(1<<(i-1))<=n) mi[j][i]=min(mi[j][i],mi[j+(1<<(i-1))][i-1]);    }}int rmq_min(int l,int r){    int k=(int)(log((r-l+1)*1.0)/log(2.0));    return min(mi[l][k],mi[r-(1<<k)+1][k]);}int main(){    while(~scanf("%d",&n)){        for(int i=1;i<=n;i++) scanf("%d%d",&p[i].fs,&p[i].se);        sort(p+1,p+n+1);        memset(mi,0,sizeof(mi));        tmp=0;        rmq_init();        goal[tmp++]=p[1];        for(int i=2;i<=n;i++){            int k=i;            while(p[i].fs==p[k].fs&&k>=1)  k--;            if(k==0) goal[tmp++]=p[i];            else{                if(rmq_min(1,k)>=p[i].se) goal[tmp++]=p[i];            }        }        printf("%d\n",tmp);        for(int i=0;i<tmp;i++) printf("%d %d\n",goal[i].fs,goal[i].se);    }    return 0;}

 

HDU3193 Find the hotel