时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
一、题目内容
题目描述
铁子从森林里收集了n根木棍，她开始将它们按顺序的排成一排，从左到右依次为1到n，她回想起
在数学课上老师教她的三角形知识，她开始从这些木棍中间找三根木棍来组成一个周长最大的三角形，
这时她的兄弟顺溜偷偷的溜了过来，偷走了第i根木棍，现在她想知道现在能够组成周长最大的三角形
的周长是多少？
输入描述
第一行两个整数n和q。
第二行n个整数表示第根木棍的长度
。
接下来q行，每行一个整数表示被顺溜偷走的木棍编号。注意每行的事件是独立的，也就是说每一次操作都是对于原来的n根木棍进行的。
输出描述
对于每个询问输出一行表示答案，如果删除木棍后无法组成三角形则输出 -1 。
示例1
输入
6 2
1 2 3 4 5 6
6
5输出
12
13
二、解题思路
关键：1.能组成三角形的组合；2.最长周长。
可以组成三角形，而且周长最长，那么我们只需要将数组升序或降序，从最大长度的木棍——>最小长度的木棍遍历，只要能组成三角形（任意两边相加大于第三边，由于是有序的数组，因此只需要将小的两个木棍长度和与大的木棍长度比较即可），即是所有木棍能组成的最大周长perimeter（因为从大到小有序遍历），同时记下最大周长的三根木棍的标号数组maxIDS，最后再比较被顺溜顺走的木棍标号，如果标号在maxIDS中，那么排除被顺走的木棍重新遍历，否则输出最大周长perimeter。（在获取最大周长时，我们可以记录下组成最大周长三根木棍的编号，降低遍历次数，但增加了内存开销。）
代码实操
#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;
}
