개구리 뛰기(codeground)

/*

★그리디 알고리즘을 사용하여 풀었다.★

=백준 점프점프 11060 번 문제와 유사하다.

*/

#include <cstdio>

#include <vector>

using namespace std;

int main() {

int t;

scanf("%d", &t);

for (int tc = 1; tc <= t; tc++) {

int n;

scanf("%d", &n);

vector<int> a(n + 1);

a[0] = 0;

for (int i = 1; i <= n; i++) {

scanf("%d", &a[i]);

}

n += 1;

int k;

scanf("%d", &k);

int ans = 0;

int cur = a[0];

for (int i = 0; i<n - 1; i++) {

if (a[i + 1] - a[i] > k) {

ans = -1;

}

}

if (ans != -1) {

for (int i = 1; i<n; i++) {

if (cur + k < a[i]) {

cur = a[i - 1];

ans += 1;

}

}

ans += 1;

}

printf("Case #%d\n", tc);

printf("%d\n", ans);

}

return 0;

}