我用暴力算法,没有超时50分其他是WA
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
void sort(vector<int> a,int left, int right);
void arraySort(vector<int> a, int left, int right, int secondLeft, int secondRight);
int main(int argc, const char * argv[]) {
// insert code here...
int n = 0;
cin >> n;
vector<int>a(n);
vector<int>countA(n-1);
for (int i = 0; i < n; i++) {
int tmp = 0;
cin >> tmp;
a[i] = tmp;
}
for (int i = 0; i < n-1;i++) {
countA[i] = abs(a[i]-a[i+1]);//计算绝对值
}
sort(countA, 0, countA.size());
for (int i = 0; i < n-1;i++) {
if (countA[i] != i+1) {
printf("Not jolly");// 差根预期的不一样,不符合欢乐的跳
return 0;
}
}
printf("Jolly");
return 0;
}
void sort(vector<int> a,int left, int right) {
if (left < right) {
int mid = (right-left)/2+left;
sort(a, left, mid);
sort(a, mid+1, right);
arraySort(a, left, mid, mid+1, right);
}
}
void arraySort(vector<int> a, int left, int right, int secondLeft, int secondRight) {
vector<int> result(0);
int i=left,j=secondLeft;
while (true) {
if (i > right) {
while (j <= secondRight) {
result.push_back(a[j]);
j++;
}
break;
}
if (j > secondRight) {
while (i <= right) {
result.push_back(a[i]);
i++;
}
break;
}
if (a[i] < a[j]) {
result.push_back(a[i]);
i++;
}else {
result.push_back(a[j]);
j++;
}
}
for (int i = 0; i < result.size(); i++) {
a[left+i] = result[i];
}
}