若有更好的錯(cuò)誤請(qǐng)指證,若有更好的想法希望可以不吝嗇的分享,感謝
另外感謝Lucky貓的 UVA（ACM）園地的翻譯
問(wèn)題
思路
題目的意思其實(shí)是要表達(dá)1n個(gè)數(shù)裡,所有兩個(gè)數(shù)之間的差值要有1n-1,那就是jolly.
所以可以用一個(gè)長(zhǎng)度為n的array紀(jì)錄1~n-1是否都存在(為了方便array[0]則捨棄不用)
version1
仔細(xì)思考可得以下幾點(diǎn):
- 若兩數(shù)差值為k,
k > length(array)-1則 not jolly (根據(jù)上述只記錄1~n-1的值所以不能大於n-1) - 記錄完所有兩數(shù)差值之後,檢查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
另一種解法一樣是使用表格記錄,只是用了不同的判斷方式:
- 在記錄兩數(shù)差值k的時(shí)候,順便去看表格,如果k本來(lái)已經(jīng)存在,則為not jolly (因?yàn)橛衝個(gè)數(shù))
- 若兩數(shù)的差值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;
}
