CCF 202109-2！

70分超时做法

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int cmp1(int x,int y) {
    return x>=y;
}
int cmp2(int x,int y) {
    return x<=y;
}
int main() {
    int n;
    cin >> n;
    vector<int> arr(n+2,0),peak = {0},valley;
    for(int i = 1;i<=n;i++) {
        cin >> arr[i];
    }
    for(int i = 1;i<=n;i++) {
        if(arr[i] > arr[i-1]) {
            int j = 1;
            while(arr[i] == arr[i+j]) {
                j++;
            }
            if(arr[i] > arr[i+j])
                peak.push_back(arr[i]);
        }
        if(arr[i] < arr[i-1]) {
            int j = 1;
            while(arr[i] == arr[i+j]) {
                j++;
            }
            if(arr[i] < arr[i+j])
                peak.push_back(arr[i]);
                valley.push_back(arr[i]);
        }
    }
    peak.push_back(0);
    valley.push_back(0);
    int max = 0;
    for(auto it = valley.begin();it != valley.end();it++) {
        int num = 0;
        for(auto pe = peak.begin()+1;pe != peak.end()-1;pe++) {
            if(*pe > *it && *(pe-1) <= *it) {
                num++;
            }
        }
        if(num >max) {
            max = num;
        }
    }
    cout << max;
    return 0;
}

100 分做法

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int cmp1(int x,int y) {
    return x>=y;
}
int cmp2(int x,int y) {
    return x<=y;
}
int main() {
    int n;
    cin >> n;
    vector<int> arr(n+2,0),peak,valley;
    for(int i = 1;i<=n;i++) {
        cin >> arr[i];
    }
    for(int i = 1;i<=n;i++) {
        if(arr[i] > arr[i-1]) {
            int j = 1;
            while(arr[i] == arr[i+j]) {
                j++;
            }
            if(arr[i] > arr[i+j])
                peak.push_back(arr[i]);
        }
        if(arr[i] < arr[i-1]) {
            int j = 1;
            while(arr[i] == arr[i+j]) {
                j++;
            }
            if(arr[i] < arr[i+j])
                valley.push_back(arr[i]);
        }
    }
    valley.push_back(0);
    sort(peak.begin(),peak.end(),cmp1);
    sort(valley.begin(),valley.end(),cmp1);
    int max = 0,j = 0;
    for(int i = 0;i < valley.size();i++) {
        for(;j<peak.size();j++) {
            if(peak[j] <= valley[i])
                break;
        }
        if(j-i >max) {
            max = j-i;
        }
    }
    cout << max;
    return 0;
}