题意
给n个数,取3个组成三角形,且要求三角形的周长是最大的和最小的。
思路
求周长最大三角形,只要将n个数从大到小排序,然后取满足构成三角形的连续三个数即可。
求周长最小三角形,将n个数从小到大排序后,取连续的两个值然后二分第三条边。
代码
int solve(int n, vector<int>& a) {//n个数,存在数组a中
sort(all(a));
LL Mx = 0, Mn = 1e18;
//求最大三角形
for(int i = 2; i < n; ++i) {
if(a[i - 1] + a[i - 2] > a[i]) {
Mx = max(Mx, (LL)a[i] + a[i - 1] + a[i - 2]);
}
}
//求最小三角形
for(int i = 1; i + 1 < n; ++i) {
int p = upper_bound(a.begin(), a.begin() + i, a[i + 1] - a[i]) - a.begin();
if(p < i) {
Mn = min(Mn, (LL)a[p] + a[i] + a[i + 1]);
}
}
}