若有更好的錯誤請指證,若有更好的想法希望可以不吝嗇的分享,感謝
另外感謝Lucky貓的 UVA（ACM）園地的翻譯
問題
思路
題目的意思其實是要表達1n個數裡,所有兩個數之間的差值要有1n-1,那就是jolly.
所以可以用一個長度為n的array紀錄1~n-1是否都存在(為了方便array[0]則捨棄不用)
version1
仔細思考可得以下幾點:
- 若兩數差值為k,
k > length(array)-1則 not jolly (根據上述只記錄1~n-1的值所以不能大於n-1) - 記錄完所有兩數差值之後,檢查1~n-1的值皆存在則為jolly
#include <iostream>
#include <cmath>
using namespace std;
bool check(int *nums,bool *record,int length){
for(int i = 1 ; i < length ; i++){
int temp = abs(nums[i] - nums[i-1]);
if(temp > length - 1)
return false;
record[temp] = true;
}
for(int i = 1 ; i < length ; i++){
if(!record[i])
return false;
}
return true;
}
int main(){
int length;
while(cin >> length){
int nums[3001] = {0};
bool record[3001]= {false};
for(int i = 0 ; i < length ; i++){
cin >> nums[i];
}
if(check(nums,record,length))
cout << "Jolly" << endl;
else
cout << "Not jolly" << endl;
}
}
version2
另一種解法一樣是使用表格記錄,只是用了不同的判斷方式:
- 在記錄兩數差值k的時候,順便去看表格,如果k本來已經存在,則為not jolly (因為有n個數)
- 若兩數的差值k,
k = 0或k > length - 1則 not jolly. - 若不為not jolly,則為 jolly
bool check(int *nums,bool *record,int length){
for(int i = 1 ; i < length ; i++){
int temp = abs(nums[i] - nums[i-1]);
if(temp > length - 1 || temp == 0 || record[temp])
return false;
record[temp] = true;
}
return true;
}
