首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。