Day5-T2

原题目

　　根据社会学研究表明，人们都喜欢和自己身高相近的人做朋友。现在有 N 名身高各不相同的同学依次走进教室。

　　调查人员想预测每个人在走入教室的瞬间最想和已经在教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。

　　比如一名身高为 180CM 的同学走进教室时，有一名身高为 179CM 的同学和一名身高为 181CM 的同学在教室里，那么这名身高为 180CM 的同学会更想和身高为 181CM 的同学做朋友。

　　对于第 1 个走进教室的同学我们不做预测。

　　第 1 行一个整数 N，表示学生的人数；第 2 行到第 N+1 行，每行一个整数，第 i+1 行为 Hi，表示第 i 名同学的身高；

　　输出共 N-1 行，第 i 行表示第 i+1 名同学最想和已经在教室里面的哪个同学做朋友；

S1：

　　Input：

　　Output：

　　Describe：链表存储。

　　code：

#include<bits/stdc++.h>

#define INF 5000005

#define rep(a,b) for(register int i=(a);i<=(b);i++)

#define per(a,b) for(register int i=(a);i>=(b);i--)

using namespace std;

int n,ans[INF],dwn[INF],Jhj[INF],up[INF];

struct fr{

	int h,num;

}a[INF];

inline bool cmp(const fr x,const fr y){

	return x.h<y.h;

}

inline int read(){

	int ret=0,f=1;char ch=getchar();

	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}

	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();

	return ret*f;

}

inline void write(int x){

    if(x/10)write(x/10);putchar(x%10+'0');

}

int main(){

    n=read();

    rep(1,n)a[i].h=read(),Jhj[i]=a[i].h,a[i].num=i;

    sort(a+1,a+n+1,cmp);

    rep(1,n)dwn[a[i].num]=a[i-1].num,up[a[i].num]=a[i+1].num;

    per(n,2){                                        //逆序！！！

    	int y=0x7fffffff,x=y;

    	if(dwn[i])x=Jhj[i]-Jhj[dwn[i]];              //Up[i]表示比第i个人高的第一个人，Dwn[i]表示比第i个人低的第一个人

    	if(up[i]&&up[i]!=n+1)

		y=Jhj[up[i]]-Jhj[i];

    	if(x<y)ans[i]=dwn[i];

    	else ans[i]=up[i];

    	up[dwn[i]]=up[i];                             //Del操作

    	dwn[up[i]]=dwn[i];

	}

	rep(2,n)write(ans[i]),putchar('\n');

    return 0;

}

巴特西

Day5-T2

最新文章

热门文章