牛客小白月赛4 A.三角形

题目链接

题目描述

铁子从森林里收集了n根木棍，她开始将它们按顺序的排成一排，从左到右依次为1到n，她回想起
在数学课上老师教她的三角形知识，她开始从这些木棍中间找三根木棍来组成一个周长最大的三角形，
这时她的兄弟顺溜偷偷的溜了过来，偷走了第i根木棍，现在她想知道现在能够组成周长最大的三角形
的周长是多少？

输入描述:

第一行两个整数n和q。(1 ≤ n, q ≤ 1e5)
第二行n个整数表示第i根木棍的长度ai。(1 ≤ ai ≤ 1e9)
接下来q行，每行一个整数表示被顺溜偷走的木棍编号。注意每行的事件是独立的，也就是说每一次操作都是对于原来的n根木棍进行的。

输出描述:

对于每个询问输出一行表示答案，如果删除木棍后无法组成三角形则输出 -1 。

示例1

输入

6 2
1 2 3 4 5 6
6
5

输出

12
13

首先找最大边长肯定是先排序，然后某一个连续的三个值构成三角形，那么可以找到这三个值的在原数组中的下标(这点很重要，因为删的是原数组的下标)，若删除这三个下标之外的，直接输出最大周长即可，否则对三种情况单独判断即可，AC代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,q,pos;
ll x,mx,ans[N];
map<ll,int>p;
vector<ll>a,b,c;
void calculate(int x){
    b.clear();
    b=a;
    b.erase(b.begin()+x-1);
    mx=0;
    for(int i=2;i<n-1;i++){
        if(b[i-1]+b[i-2]>b[i]){
            ll c=b[i]+b[i-1]+b[i-2];
            if(c>mx) mx=c;
        }
    }
    ans[x]=(mx?mx:-1);
}

int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++) scanf("%lld",&x),a.push_back(x);
    c=a;
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++) p[a[i]]=i+1;
    mx=0;
    for(int i=2;i<n;i++){
        if(a[i-1]+a[i-2]>a[i]){
            ll c=a[i]+a[i-1]+a[i-2];
            if(c>mx) mx=c,pos=i+1;
        }
    }
    if(!mx) memset(ans,-1,sizeof(ans));
    else{
        for(int i=1;i<=n;i++) if(i<pos-2||i>pos) ans[i]=mx;
        calculate(pos),calculate(pos-1),calculate(pos-2);
    }
    while(q--){
        scanf("%d",&x);
        printf("%lldn",ans[p[c[x-1]]]);
    }
}

最后

以上就是碧蓝小鸭子为你收集整理的牛客小白月赛4 A.三角形牛客小白月赛4 A.三角形的全部内容，希望文章能够帮你解决牛客小白月赛4 A.三角形牛客小白月赛4 A.三角形所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。