G--我要去内蒙古大草原

G--我要去内蒙古大草原

时间： 1ms        内存：128M

描述：

春天到了，小明想要从烟台开车去内蒙古大草原放松一下，这两地的距离是1422公里。小明的座驾每跑200公里必须加油。在烟台有加油站可以加满油，路上也有一些加油站。请你帮忙计算一下，小明能不能把车开到内蒙古再开回来。

输入：

多组测试数据。
每组测试数据第一行为n，表示加油站的个数；接着是n行整数，表示加油站到烟台的距离，取值范围是0到1422，没有两个加油站在同一位置。
最后一组测试数据后以0结束。

输出：

如果小明能完成这次旅行，输出POSSIBLE，不能完成输出IMPOSSIBLE 。

示例输入：

2
0
900
8
1400
1200
1000
800
600
400
200
0
0

示例输出：

IMPOSSIBLE
POSSIBLE

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
int main(){
	int i,j,a[1422];
	int n;
	while(~scanf("%d",&n))
	{
		if(!n)break;
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(i=0;i<n-1;i++)
			for(j=i+1;j<n;j++)
				if(a[i]>a[j])
				{
					int t=a[i];
					a[i]=a[j];
					a[j]=t;
				}
		a[n]=(1422-a[n-1])*2;
		for(i=n-1;i;i--)
			a[i]=a[i]-a[i-1];
		a[0]+=200;
		for(i=0;i<=n;i++)
			if(a[i]>200)
				break;
			printf(i!=n+1?"IMPOSSIBLE\n":"POSSIBLE\n");
	}
return 0;}

参考答案（时间最优[0]）：

#include <iostream>
using namespace std;
int main()
{
	int T,i,j,temp;
	int dis[1423];
	while((cin>>T)&&T!=0)
	{
		for(i=0;i<T;i++)
		{
			cin>>dis[i];
		}
		for(i=0;i<T;i++)
		{
			temp=i;
			for(j=i;j<T;j++)
			{
				if(dis[temp]>dis[j])
					temp=j;
			}
			j=dis[i];
			dis[i]=dis[temp];
			dis[temp]=j;
		}
		for(i=0;i<T-1;i++)
		{
			if(dis[0]!=0)
			{
				cout<<"IMPOSSIBLE"<<endl;
				break;
			}
			if((dis[i+1]-dis[i])>200)
			{
				cout<<"IMPOSSIBLE"<<endl;
				break;
			}
			if((dis[T-1]+200)<1422)
			{
				cout<<"IMPOSSIBLE"<<endl;
				break;
			}
			if(2*(1422-dis[T-1])>200)
			{
				cout<<"IMPOSSIBLE"<<endl;
				break;
			}
		}
		if(i==T-1)
			cout<<"POSSIBLE"<<endl;
	}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。