UVA 10038: Jolly Jumpers

Jasonlin posted @ 2011年3月27日 12:55 in UVA , 3447 阅读

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=979&mosmsg=Submission+received+with+ID+8683259

题目大意:

      n长度数列中相邻的数之间的差的绝对值在1~n-1范围内且不一样,这样的数列叫 jolly jumper。

解题思路:

      用一个数组标记各个绝对值是否出现过,要是出现过就不是 jolly jumper,超出1~n-1的范围也不是 jolly jumper 。题目没看清楚错了一次。此题用到基础的hash算法思维。

解题代码:

#include<iostream>
using namespace std;
bool s[3001];
int a[3001];
int main(){
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>a[i];			
			s[i]=true;
		}
		bool flag=true;
		for(int i=2;i<=n;i++){
				int x=(a[i]-a[i-1]>0)?(a[i]-a[i-1]):(a[i-1]-a[i]);
				if(x==0||x>n-1){
					flag=false;
					break;
				}
				else{
					if(s[x])
						s[x]=false;
					else{
						flag=false;
						break;
					}
				}
		}
		if(flag)
			cout<<"Jolly"<<endl;
		else
			cout<<"Not jolly"<<endl;
	}
}

扩展知识:http://blog.csdn.net/hqd_acm/archive/2010/09/23/5901955.aspx

  • 无匹配
  • 无匹配
metaphysis 说:
2011年4月13日 12:27

对应下列测试用例,你的程序输出不正确:
1 5
0 1 3 2 4

Avatar_small
comathlish 说:
2011年4月14日 17:22

你的测试数据是非法的阿~ 点击链接看下原题~


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter