#include <bits/stdc++.h> int brutal_force(std::vector<int> v, int n, bool start) { // std::cerr << "run with up = " << start << "\n"; int prev = v[0]; bool up = start; int sum = 0; for(int i=1;i<n;i++) { int& cur = v[i]; // std::cerr << "i = " << i << "\tcur=" << cur << "\tprev = " << prev << "\t" << (up ? "UP" : "DOWN") << "\t"; int next = 0; if(i+1 != 0) { next = v[i+1]; // std::cerr << "next = " << next << "\t"; } if(up && cur <= prev) { // std::cerr << "UP & LE"; sum++; if(i+1 != 0) { int max = std::max(prev, next); cur = max+1; } else cur = 1000001; // std::cerr << "\tcur = " << cur << "\t"; } else if(!up && cur >= prev) { // std::cerr << "!UP & GE"; sum++; if(i+1 != 0) { int min = std::min(prev, next); cur = min-1; } else cur = -1000001; // std::cerr << "\tcur = " << cur << "\t"; } // std::cerr << "\n"; prev = cur; up = !up; } // std::cerr << "sum = " << sum << "\n===\n"; return sum; } int main() { std::ios_base::sync_with_stdio(0); int n; std::cin >> n; std::vector<int> v(n); for(int i=0;i<n;i++) { std::cin >> v[i]; } int a = brutal_force(v, n, true); int b = brutal_force(v, n, false); int sum = std::min(a, b); std::cout << sum << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <bits/stdc++.h> int brutal_force(std::vector<int> v, int n, bool start) { // std::cerr << "run with up = " << start << "\n"; int prev = v[0]; bool up = start; int sum = 0; for(int i=1;i<n;i++) { int& cur = v[i]; // std::cerr << "i = " << i << "\tcur=" << cur << "\tprev = " << prev << "\t" << (up ? "UP" : "DOWN") << "\t"; int next = 0; if(i+1 != 0) { next = v[i+1]; // std::cerr << "next = " << next << "\t"; } if(up && cur <= prev) { // std::cerr << "UP & LE"; sum++; if(i+1 != 0) { int max = std::max(prev, next); cur = max+1; } else cur = 1000001; // std::cerr << "\tcur = " << cur << "\t"; } else if(!up && cur >= prev) { // std::cerr << "!UP & GE"; sum++; if(i+1 != 0) { int min = std::min(prev, next); cur = min-1; } else cur = -1000001; // std::cerr << "\tcur = " << cur << "\t"; } // std::cerr << "\n"; prev = cur; up = !up; } // std::cerr << "sum = " << sum << "\n===\n"; return sum; } int main() { std::ios_base::sync_with_stdio(0); int n; std::cin >> n; std::vector<int> v(n); for(int i=0;i<n;i++) { std::cin >> v[i]; } int a = brutal_force(v, n, true); int b = brutal_force(v, n, false); int sum = std::min(a, b); std::cout << sum << "\n"; return 0; } |