三角形

2020-12-17

三角形

题意

题目就是给出一个数组，要从中找出三个数组成三角形，问这个三角形的最大周长和最小周长之差是多少
数据保证能组成三角形

题解

首先对数组进行排序，先找最大的三角形，先看最大的三个数a,b,c(a <= b <= c)
如果a + b > c说明他们可以组成三角形，即最大的周长就是a + b + c
如果不能组成三角形，则必然是c太大了，因为此时a和b就是剩下的所有数中，最大的两个，而此时a + b <= c，说明只要选了c，必然找不到两个数可以和c组成三角形，所以毫不犹豫的舍弃c，然后看剩下的数中最大的三个数，如此反复，直到能组成三角形
这里的三条边是连续的三个数，如果不能组成三角形直接舍弃最大边

在看最小三角形还是规定三条边a,b,c(a <= b <= c)，所以它们的下标x,y,z是(x < y < z)
如果此时a,b,c可以组成三角形，且z = y + 2，那么可以推断array[x] + array[y] > array[y + 2]，也可以推断出array[x] + array[y] > array[y + 1]，由于array[y + 1] <= array[y + 2]，所以后者是更好的选择
到这里可以推断出，最小三角形的最大的两条边是连续的，即z = y + 1，那么最小的那条边a >= c - b + 1，并且此时a的下标不能超过y，等于都不可以
这里的b和c是连续的，利用这一点反过来推断a的大小和位置，如果找得到满足条件的数，说明最小三角形就找到了，否则就往后看

优化

对于斐波那契数列，a[i + 1] = a[i] + a[i - 1]，此时根据较大的两条边确定第三条边为(a[i + 1] - a[i] + 1) = (a[i - 1] + 1), (a[i - 1] + 1)的下标刚好不比a[i]的下标i小，所以对于斐波那契数列，是一直都无法组成三角形的，而斐波那契数列的第50项就爆int了，所以如果存在合法的最小三角形，那么前50项左右就可以找到了
同理，最大三角形也是如此，后50项左右就可以出答案了
所以只需要用两次循环分别求最大最小周长就可以了，用一次循环找的话会慢一点

卡bug

由于此题的数据太弱，像是<1,2,3,5,5>,<1,2,4,4,4>这种的数据完全没有，所以对最小三角形取三个连续的数判断，不满足则舍弃最小，这种做法也是能过题的

代码

牛客正确ac代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型vector 代表n个数的大小
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        int b[1020];
        for (int i = 0; i < n; i++)    b[i] = a[i];
        sort(b, b + n);
        int ma = 0, mm = 0;
        for (int i = 1; i < n - 1; i++) {
            int tmp = b[i + 1] - b[i] + 1;
            int pos = lower_bound(b, b + i, tmp) - b;
            if (pos < i) {
                mm = b[pos] + b[i] + b[i + 1];
                break;
            }
        }
        for (int i = n - 2; i > 0; i--) {
            if (b[i - 1] + b[i] > b[i + 1]) {
                ma = b[i - 1] + b[i] + b[i + 1];
                break;
            }
        }
        return ma - mm;
    }
};

牛客卡bug ac代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型vector 代表n个数的大小
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        sort(a.begin(), a.end());
        long long min_sum, max_sum;
        for (int i = 0; i < int(a.size()) - 2; i ++)
            if (a[i + 2] < a[i] + a[i + 1]) {
                min_sum = (long long)a[i] + a[i + 1] + a[i + 2];
                break ;
            }
        for (int i = int(a.size()) - 3; i >= 0; i --)
            if (a[i + 2] < a[i] + a[i + 1]) {
                max_sum = (long long)a[i] + a[i + 1] + a[i + 2];
                break ;
            }
        return max_sum - min_sum;
    }
};

完整代码

#include<bits/stdc++.h>
using namespace std;

const int N = 5e3 + 20;

int a[N], n;

int main () {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        sort(a, a + n);
        int ma = -1, mm = -1;
        for (int i = 1; i < n - 1; i++) {
            int tmp = a[i + 1] - a[i] + 1;
            int pos = lower_bound(a, a + i, tmp) - a;
            if (pos < i) {
                mm = a[pos] + a[i] + a[i + 1];
                ///printf("%d, %d, %d\n", a[pos], a[i], a[i + 1]);
                break;
            }
        }
        for (int i = n - 2; i > 0; i--) {
            if (a[i] + a[i - 1] > a[i + 1]) {
                ma = a[i - 1] + a[i] + a[i + 1];
                ///printf("%d, %d, %d\n", a[i - 1], a[i], a[i + 1]);
                break;
            }
        }
        printf("%d\n", ma - mm);
    }
    return 0;
}

/**
5
1 2 3 5 5

5
1 2 4 4 4

10
1 1 2 3 5 8 13 21 34 55

6
1 2 3 4 5 6


**/