拼三角

题目链接：nowcoder 219046

到主站看：https://blog.csdn.net/weixin_43346722/article/details/116171759

题目大意

给你 6 个数，分你能不能分成两组各三个数，使得每组以这三个数为边长都可以构成三角形。

思路

就直接暴搜出每一种分组情况然后判断。
判断能否构成三角形就是两个短的边相加大于第三条边。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int T, a[11];
int l[11], r[11];

bool cmp(int x, int y) {
    return x < y;
}

bool dfs(int now) {
    if (now > 6 && l[0] == 3 && r[0] == 3) {
        int ll[11] = {0, l[1], l[2], l[3]}, rr[11] = {0, r[1], r[2], r[3]};
        sort(ll + 1, ll + 3 + 1, cmp);//按边排序
        sort(rr + 1, rr + 3 + 1, cmp);
        if (ll[1] + ll[2] > ll[3] && rr[1] + rr[2] > rr[3]) return 1;//能构成三角形就是要满足短的两条边加起来大于第三条边
            else return 0;
    }
    if (now > 6) return 0;

    if (l[0] <= 2) {//dfs 暴搜放第一组
        l[++l[0]] = a[now];
        if (dfs(now + 1)) return 1;
        l[l[0]--] = 0;
    }
    if (r[0] <= 2) {//dfs 暴搜放第二组
        r[++r[0]] = a[now];
        if (dfs(now + 1)) return 1;
        r[r[0]--] = 0;
    }

    return 0;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));

        for (int i = 1; i <= 6; i++)
            scanf("%d", &a[i]);

        if (dfs(1)) printf("Yes\n");
            else printf("No\n");
    }

    return 0;
}