算是簡單版本的前置問題LeetCode盛最多水的容器(/雙指針)

付費oj地址

公元2919年，人類終於發現了一顆宜居星球——X星。
現想在X星一片連綿起伏的山脈間建一個天熱蓄水庫，如何選取水庫邊界，使蓄水量最大？

要求：

        山脈用正整數數組s表示，每個元素代表山脈的高度。
        選取山脈上兩個點作為蓄水庫的邊界，則邊界內的區域可以蓄水，蓄水量需排除山脈佔用的空間
        蓄水量的高度為兩邊界的最小值。
        如果出現多個滿足條件的邊界，應選取距離最近的一組邊界。
輸出邊界下標（從0開始）和最大蓄水量；如果無法蓄水，則返回0，此時不返回邊界。
例如，當山脈為s=[3,1,2]時，則選取s[0]和s[2]作為水庫邊界，則蓄水量為1，此時輸出：0 2:1
當山脈s=[3,2,1]時，不存在合理的邊界，此時輸出：0。

給定一個長度為 n 的整數數組 height 。數組的元素表示山的高度，選擇兩個元素作為水庫的邊界，求蓄水量的最大值並輸出蓄水量最大時的邊界下標（蓄水量相同時輸出下標較近的）。

輸入描述：

輸入一行數字，空格分隔。

輸出描述：

輸出蓄水量的最大值及輸出蓄水量最大時的邊界下標

示例1：

輸入：

1 8 6 2 5 4 8 3 7 

輸出：

1 6:15

説明：蓄水量的最大值為 15

蓄水量最大時的邊界下標為1 和 6

十個測試數據，wa1了

#include<bits/stdc++.h>
#include <cctype>
#include <cmath>
#include<algorithm>
using namespace std;
#define N 10000
int lans[N], rans[N], a[N][N];
int Lans = 0x3f3f3f3f, Rans = 0x3f3f3f3f;
int mount[N];
int t;

int main(){

    int n = 0, l = 0;
    memset(lans, 0x3f, sizeof lans);
    memset(rans, 0x3f, sizeof rans);
    // int ANS = 0;
    while(cin >> t){
        mount[n ++] = t;
    }
    int maxm = 0;
    int flag = 1;
    for(int i = 0; i < n; i ++){
        for(int j = i + 2; j < n; j ++){
            int ans = 0;
            int minm = min(mount[i], mount[j]);
            // cout << minm << endl;
            ans = (j - i - 1) * minm;
            // cout << ans << " ";
            for(int k = i + 1; k < j; k ++){
                // cout << mount[k] << " ";
                if (mount[k] > minm) {
                    ans -= minm;
                }else{
                    ans -= mount[k];
                }
            }
            a[i][j] = ans;
            // cout << ans << endl;
            // cout << endl;
            maxm = max(maxm, ans);
            // if(ans > maxm){
            //     if(flag){
            //         lans[l ++] = i;
            //         rans[l ++] = j;
            //         flag = 0;
            //         cout << i << " " << j << endl;
            //     }
            //     else if(maxm == ans){
            //         lans[l ++] = i;
            //         rans[l ++] = j;
            //         cout << i << " " << j << endl;
            //     }
            //     maxm = ans;
            // }
            // cout << maxm << endl;
        }
        // ANS = maxm;
    }
    for(int i = 0; i < n; i ++){
        for(int j = i + 2; j < n; j ++){
            if(a[i][j] == maxm){
                lans[l ++] = i;
                rans[l ++] = j;
            }
        }
    }
    for(int i = 0 ; i < l; i ++){
        Lans = min(Lans, lans[i]);
        Rans = min(Rans, rans[i]);
    }
    // cout << Lans << " " << Rans;
    // cout << ANS;
    // for(int i = 0; i < n; i ++)
    //     cout << mount[i] << " ";
    // Lans Rans:maxm or 0
    if(maxm != 0){
        cout << Lans << " " << Rans << ":" << maxm;
    }else{
        cout << maxm;
    }
    return 0;
}

沒找到能ac的我放棄了。。。

#include<bits/stdc++.h>
#include <cctype>
#include <cmath>
#include<algorithm>
using namespace std;
#define N 100000
int lans[N], rans[N], a[1000][1000];
int Lans = 0x3f3f3f3f, Rans = 0x3f3f3f3f;
int mount[N];
int t;

int main(){

    int n = 0, l = 0;
    memset(lans, 0x3f, sizeof lans);
    memset(rans, 0x3f, sizeof rans);
    // int ANS = 0;
    while(cin >> t){
        mount[n ++] = t;
    }
    int maxm = 0;
    int flag = 1;
    for(int i = 0; i < n; i ++){
        for(int j = i + 2; j < n; j ++){
            int ans = 0;
            int minm = min(mount[i], mount[j]);
            ans = (j - i - 1) * minm;
            for(int k = i + 1; k < j; k ++){
                if (mount[k] > minm) {
                    ans -= minm;
                }else{
                    ans -= mount[k];
                }
            }
            a[i][j] = ans;
            maxm = max(maxm, ans);
        }
    }
    for(int i = 0; i < n; i ++){
        for(int j = i + 2; j < n; j ++){
            if(a[i][j] == maxm){
                lans[l ++] = i;
                rans[l ++] = j;
            }
        }
    }
    for(int i = 0 ; i < l; i ++){
        Lans = min(Lans, lans[i]);
        Rans = min(Rans, rans[i]);
    }
    if(maxm != 0){
        cout << Lans << " " << Rans << ":" << maxm;
    }else{
        cout << maxm;
    }
    return 0;
}