牛客小白月赛4a-三角形（模拟）

本文主要是介绍牛客小白月赛4a-三角形（模拟），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

复制

6 2
1 2 3 4 5 6
6
5

输出

复制

12
13

思路：排序是一定要排的，为了保证排序过后原来木棍的编号不变，我们就要用结构体来存木棍的长度和编号。然后sort排序

至于判断能否构成三角形，只需要较小的那两个边之和大于第三条边即可，如果满足条件就输出，否则就让sum减去最大的那个边（已经排过序了，离最大边最近的两个边之和都小于它，其他边更不满足）往下遍历，找不到就输出-1。

记得把sum开成long long

ACDAIMA:

#include <iostream>
#include <algorithm>
#define maxn 100005
using namespace std;
struct node
{int v;int x;bool operator <(const node &a)const{return v < a.v;}
}a[maxn];int main()
{int n,q;scanf("%d%d",&n, &q);for(int i = 1; i <= n; i++){scanf("%d",&a[i].v);a[i].x = i;}sort(a+1,a+n+1);while(q--){int s, cn = 0;bool flag = false;long long sum = 0;scanf("%d", &s);for(int i = n; i > 0; i--){if(a[i].x != s){sum += a[i].v;cn++;}if(cn == 3){if(a[i].v + a[i+1].v > a[i+2].v){printf("%lld\n", sum);flag = true;break;}else{sum -= a[i+2].v;cn--;}}         }if(!flag) printf("-1\n");}return 0;
}

这篇关于牛客小白月赛4a-三角形（模拟）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！