Day4-T2

原题目

　　某大厦共有 N 层，现在知道共有 K 个请求要上下电梯；下面告诉你每个请求乘电梯的出发层次和结束层次。请你求出整个电梯的运行过程。假设电梯一开始停在第一层，运行 K 个请求最后回到第一层。

　　例如有个 9 个层次的电梯，共接收到 5 个请求。

　　1 5（表示要求从 1 层到 5 层）

　　4 2

　　2 8

　　6 9

　　5 1

　　那么电梯的运行路线为：1-2-5-6-8-9-5-4-2-1

　　第一行为 N 和 K；后面每行两个整数 x y 表示 K 个请求，每个请求保证合理.且肯定有请求从第一层出发，也肯定有请求回到第一层结束。但不一定能够达到最高层，数据保证解的唯一性。

　　电梯的运行过程，要求从第一层开始，最后回到第一层，每两个数据之间用"-"间隔，行首和行末不要有多余的"-"（"-"为减号）。

S1：

　　Input：

　　Output：

1---------1

　　Describe：

　　code：

#include<bits/stdc++.h>

#define INF 214748364

#define eps 1e-9

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

#define rep2(a,b) for(register int j=(a);j<=(b);j++)

using namespace std;

int n,k,ii=1,tot,maxx=-1;

int tp[1000111],f[1000101];

struct BDF{

	int l,r;

	bool wy;

}a[1001001];

inline bool cmp(BDF a,BDF b){

	if(a.wy!=b.wy)return a.wy>b.wy;

	else if(!a.wy)return a.l>b.l;

	else return a.l<b.l;

}

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 double read2(){

    double X=0,Y=1.0;int w=0;char ch=0;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=X*10+(ch^48),ch=getchar();

    ch=getchar();

    while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();

    return w?-X:X;

}

inline void write(int x){

	if(x<0){putchar('-');write(-x);return;}

    if(x/10) write(x/10);

    putchar(x%10+'0');

}

int main(){

    freopen("lift.in","r",stdin);

    freopen("lift.in","w",stdout);

    n=read(),k=read();

    for(int i=1;i<=k;i++)                                                  //分类成上行和下行讨论

    {

    	a[i].l=read();

    	a[i].r=read();

    	if(a[i].l<a[i].r)a[i].wy=1;

    	else a[i].wy=0;

	}

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

//	for(int i=1;i<=n;i++)

//	cout<<a[i].l<<' '<<a[i].r<<' ';

	while(a[ii].wy&&ii<=k){                                                //上行桶排

		tp[a[ii].l]++;

		tp[a[ii].r]++;

		maxx=max(maxx,a[ii].r);                                            //存储上行终点

		ii++;

	}

	for(int i=1;i<=100000;i++)                                             //导入数组

	if(tp[i])f[++tot]=i;

	ii=k;

	memset(tp,0,sizeof(tp)); 

	while(!a[ii].wy&&ii>=1){                                               //下行桶排

		tp[a[ii].l]++;

		tp[a[ii].r]++;

		if(a[ii].l>maxx)maxx=-1;                                           //数据有锅，不加这句话AC，但理论上应该特判 （若上行终点不是下行起点且比下行起点低，如果下行也有上行终点相同楼层也要输出，但数据不特判）

		ii--;

	}

	for(int i=100000;i>=1;i--)                                             //导入数组

	if(tp[i]&&i!=maxx)f[++tot]=i;                                          //特判

	for(int i=1;i<=tot-1;i++)

	cout<<f[i]<<"-";

	cout<<f[tot];return 0;

    return 0;

}

巴特西

Day4-T2

最新文章

热门文章