题解：P10878 [JRKSJ R9] 在相思树下 III

· · 题解

10 分做法：

暴力枚举每一种情况，然后求出最大值。

代码：

#include<iostream>
#include<vector>

using namespace std;

int n, m, t, ans = 0;
vector<int> vec;

void dfs(vector<int> v, int m){
    //v 表示当前的序列，m 表示还可以操作 1 的次数。 
    if(v.size() == 1){//剩下一个元素，就可以回溯。 
        ans = max(ans, v[0]);//取最大值。 
        return;
    }
    vector<int> v1, v2;
    for(int i = 0; i < v.size()-1; i++){ 
        v1.push_back(max(v[i], v[i+1])); //操作 1 的序列。 
        v2.push_back(min(v[i], v[i+1])); //操作 2 的序列。 
    } 
    if(m > 0) dfs(v1, m-1); 
    dfs(v2, m);
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> t;
        vec.push_back(t);
    }
    dfs(vec, m);
    cout << ans;
    return 0;
}

40 分做法：

观察样例，可以发现先做 m 次操作 1 一定是最优的，所以我们只需要先暴力的做 m 次操作 1，再做 n-m-1 次操作 2，输出剩下的数就行了。

代码：

#include<iostream>

using namespace std;

const int N = 5010;
int n, m, a[N], top;

int main(){
    cin >> n >> m;
    top = n; //top 表示最后一个元素下标 +1。 
    for(int i = 0; i < n; i++) cin >> a[i];
    while(m--){//先做 m 次操作 1。 
        for(int i = 0; i < top-1; i++) a[i] = max(a[i], a[i+1]);
        top--;
    }
    while(top > 1){// 再做操作 2 直到只有一个元素 
        for(int i = 0; i < top-1; i++) a[i] = min(a[i], a[i+1]);
        top--;
    }
    cout << a[0];
    return 0;
}

特殊性质做法：

观察到 a_i \le 10，考虑枚举每一个答案，因为先做 m 次操作 1 一定是最优的，所以只要所有大于等于枚举答案的元素的间距全部小于 m 我们就可以判断出这个答案可能出现。

代码：

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], ans = 0;

bool check(int x){// 判断 x 是否可能是答案。 
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(a[i] < x) cnt++;
        else cnt = 0;
        if(cnt > m) return false;
        // 如果间距大于 m 说明 x 不可能是答案。
    }
    return true;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 10; i >= 1; i--){
        if(check(i)){cout << i; break;}
    }
    return 0;
}

满分做法：

上面的特殊性质引导了我们可以枚举答案，又由于 a_i \le 10^9 这个范围非常大，所以考虑二分答案。

又因为前面的做法小于等于答案的会判定为可能是答案，大于答案的会判定为不可能是答案，所以可以用二分答案的做法。

代码：

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], ans = 0;

bool check(int x){ 
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(a[i] < x) cnt++;
        else cnt = 0;
        if(cnt > m) return false;
    }
    return true;
} 

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    int l = 0, r = 1e9;
    while(l <= r){
        int mid = (l + r) / 2; 
        if(check(mid)){
            l = mid + 1;
            ans = mid;
        } 
        else{ 
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}