時間限制：C/C++ 1秒谁帕，其他語言2秒
空間限制：C/C++ 262144K隘谣，其他語言524288K

一蝉稳、題目內(nèi)容

題目描述

鐵子從森林里收集了n根木棍，她開始將它們按順序的排成一排劳闹，從左到右依次為1到n院究，她回想起
在數(shù)學課上老師教她的三角形知識，她開始從這些木棍中間找三根木棍來組成一個周長最大的三角形本涕，
這時她的兄弟順溜偷偷的溜了過來业汰，偷走了第i根木棍，現(xiàn)在她想知道現(xiàn)在能夠組成周長最大的三角形
的周長是多少菩颖？

輸入描述

第一行兩個整數(shù)n和q样漆。
第二行n個整數(shù)表示第根木棍的長度。
接下來q行位他，每行一個整數(shù)表示被順溜偷走的木棍編號氛濒。注意每行的事件是獨立的产场，也就是說每一次操作都是對于原來的n根木棍進行的鹅髓。

輸出描述

對于每個詢問輸出一行表示答案舞竿，如果刪除木棍后無法組成三角形則輸出 -1 。

示例1

輸入

6 2
1 2 3 4 5 6
6
5

輸出

12
13

二窿冯、解題思路

關(guān)鍵：1.能組成三角形的組合骗奖；2.最長周長。
可以組成三角形醒串，而且周長最長执桌，那么我們只需要將數(shù)組升序或降序，從最大長度的木棍——>最小長度的木棍遍歷芜赌，只要能組成三角形（任意兩邊相加大于第三邊仰挣，由于是有序的數(shù)組，因此只需要將小的兩個木棍長度和與大的木棍長度比較即可）缠沈，即是所有木棍能組成的最大周長perimeter（因為從大到小有序遍歷）膘壶，同時記下最大周長的三根木棍的標號數(shù)組maxIDS，最后再比較被順溜順走的木棍標號洲愤，如果標號在maxIDS中颓芭，那么排除被順走的木棍重新遍歷，否則輸出最大周長perimeter柬赐。（在獲取最大周長時亡问，我們可以記錄下組成最大周長三根木棍的編號，降低遍歷次數(shù)肛宋，但增加了內(nèi)存開銷州藕。）

代碼實操

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
struct Node {
    int id;
    ll l;
    bool friend operator < (Node n, Node m) {
        if (n.l == m.l) return n.id > m.id;
        return n.l < m.l;
    }
}a[MAXN];
  
int n, q;
///最長周長
ll perimeter = -1;
Node maxIDS[3];
 
void solve(int lost) {
    if (perimeter == -1) {
            cout << "-1" << endl;
        } else {
            if (maxIDS[0].id == lost || maxIDS[1].id == lost || maxIDS[2].id == lost) {
                int minL = a[maxIDS[0].l].l;
                int maxIndex = maxIDS[2].l;
                if (maxIDS[0].id == lost) {
                    minL = a[maxIDS[1].l].l;
                }
                  
                int maxL = a[maxIDS[2].l].l;
                if (maxIDS[2].id == lost) {
                    maxL = a[maxIDS[1].l].l;
                    maxIndex = maxIDS[1].l;
                }
                if (maxIDS[0].l > 1) {
                    if (a[maxIDS[0].l - 1].l + minL > maxL) {
                        cout << 1LL * a[maxIDS[0].l - 1].l + minL + maxL << endl;
                    } else {
                        int res = 0;
                        for(int i = maxIndex; i > 1; i--) {
                            if (a[i].id == lost) {
                                if (a[i - 1].l < a[i - 2].l + a[i - 3].l) {
                                    cout << 1LL * a[i - 1].l + a[i - 2].l + a[i - 3].l << endl;
                                    res = 1;
                                    break;
                                }
                            } else if (a[i - 1].id == lost) {
                                if (a[i].l < a[i - 2].l + a[i - 3].l) {
                                    cout << 1LL * a[i].l + a[i - 2].l + a[i - 3].l << endl;
                                    res = 1;
                                    break;
                                }
                            } else if (a[i - 2].id == lost) {
                                if (a[i].l < a[i - 1].l + a[i - 3].l) {
                                    cout << 1LL * a[i].l + a[i - 1].l + a[i - 3].l << endl;
                                    res = 1;
                                    break;
                                }
                            } else {
                                if (a[i].l < a[i - 1].l + a[i - 2].l) {
                                    cout << 1LL * a[i].l + a[i - 1].l + a[i - 3].l << endl;
                                    res = 1;
                                    break;
                                }
                            }
                        }
                        if (!res) cout << "-1" << endl;
                    }
                } else {
                    cout << "-1" << endl;
                }
            } else {
                cout << perimeter << endl;
            }
        }
}
  
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        cin >> a[i].l;
        a[i].id = i;
    }
    sort(a,a + n);
    for(int i = n - 1; i > 1; i--) {
        if (a[i - 2].l + a[i - 1].l > a[i].l) {
            perimeter = 1LL * a[i].l + a[i - 1].l + a[i - 2].l;
            maxIDS[0].id = a[i - 2].id, maxIDS[0].l = i - 2;
            maxIDS[1].id = a[i - 1].id, maxIDS[1].l = i - 1;
            maxIDS[2].id = a[i].id,     maxIDS[2].l = i;
            break;
        }
    }
    int lost;
    while(q--) {
        cin >> lost;
        lost -= 1;
        solve(lost);
    }
    return 0;
}