【100%通过率】华为OD机试真题 C++ 实现【最多组合直角三角形个数】【2023 Q1 | 100分】

﹏ヽ暗。殇╰゛Y 2023-09-23 23:27 38阅读 0赞

**所有题目均有五种语言实现。[C实现目录][C]、[C++ 实现目录][C_]、[Python实现目录][Python]、[Java实现目录][Java]、[JavaScript实现目录][JavaScript]**

## 题目 ##

> **题目描述**
> 
> 有N条线段，长度分别为a\[1\]-a\[n\]。  
> 现要求你计算这N条线段最多可以组合成几个直角三角形。  
> **每条线段只能使用一次**，每个三角形包含三条线段。
> 
> **输入描述**  
> 第一行输入一个正整数T(1<=T<=100)，表示有T组测试数据.  
> 对于每组测试数据，接下来有T行，  
> 每行第一个正整数N，表示线段个数(3<=N<=20)，接着是N个正整数，表示每条线段长度，(0<a\[i\]<100)。
> 
> **输出描述**  
> 对于每组测试数据输出一行，每行包括一个整数，表示最多能组合的直角三角形个数
> 
> **示例1：输入输出示例仅供调试，后台判题数据一般不包含示例**  
> 输入
> 
> 1
> 
> 7 3 4 5 6 5 12 13  
> 输出
> 
> 2
> 
> ![9bd3845cf20c4a8f8420d420cf885ef4.jpeg][]

## 思路 ##

> 1：简单题，直接全组合就可以了，leetcode上也有类似的题目：[leetcode40][]

## 考点 ##

> 1：全组合

## Code ##

#include<iostream>
    #include<vector>
    #include<stdlib.h>
    #include<algorithm>
    #include<string.h>
    #include<exception> 
    #include<map>
    #include<cmath>
    #include<unordered_map>
    #include<set>
    #include<climits>
    #include<numeric>
    #include<ctype.h>
    #include<queue>
    #include<stack>
    #include<list>
    #include<bitset>
    using namespace std;
     
    vector<int> split(string input_str) {
        vector<int> v;
        while (input_str.find(" ") != string::npos) {
            int found = input_str.find(" ");
            v.push_back(stoi(input_str.substr(0, found)));
            input_str = input_str.substr(found + 1);
        }    
        v.push_back(stoi(input_str));
        return v;
    }
     
    vector<string> split_str(string params_str, string op) {
        vector<string> p;
        while (params_str.find(op) != string::npos) {
            int found = params_str.find(op);
            p.push_back(params_str.substr(0, found));
            params_str = params_str.substr(found + 1);
        }    
        p.push_back(params_str);
        return p;
    }
     
    //二叉树节点定义
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
    };
     
    // 并查集
    class UF {
    public:
        vector<int> item;
        int count;
        
        UF(int n) : count(n){
            item = vector<int>(n + 1, 0);
            for (int i = 0; i < n; i++) item[i] = i;
        }
     
        int find(int x) {
            if (x != item[x]) {
                return (item[x] = find(item[x]));
            }
            return x;
        }
     
        void union_connect(int x, int y) {
            int x_item = find(x);
            int y_item = find(y);
        
            if (x_item != y_item) {
                item[y_item] = x_item;
                count--;
            }
        }
    };
     
    int dfs(vector<int> lines, int index) {
        int maxVal = 0;
        int a, b, c;
        for (int i = index; i < lines.size()-2; i++) {
            a = lines[i];
            if (a == 0) {
                continue;
            }
            for (int j = i+1; j < lines.size()-1; j++) {
                b = lines[j];
                if (b == 0) {
                    continue;
                }
                for (int k = j+1; k < lines.size(); k++) {
                    c = lines[k];
                    if (c == 0) {
                        continue;
                    }
                    if ((a*a + b*b) == c*c) {
                        lines[i]=0;
                        lines[j]=0;
                        lines[k]=0;
                        maxVal = max(maxVal, dfs(lines,i+1) +1);
                        lines[i]=a;
                        lines[j]=b;
                        lines[k]=c;
                    };
                }
            }
        }
    
        return maxVal;
    }
     
    int main() {
        // 处理输入
        int T;
        cin >> T;
        for (int i=0;i<T;i++) {
            int N;
            cin >> N;
            vector<int> nums;
            for (int j = 0; j < N; j++) {
                int a;
                cin >> a;
                nums.push_back(a);
            }
            
            sort(nums.begin(), nums.end());
           
            cout << dfs(nums,0)<<endl;
        }
        return 0;
    }

### 要求 ###

> 时间限制：C/C++ 1秒，其他语言 2秒
> 
> 空间限制：C/C++262144K，其他语言524288K
> 
> 64bit IO Format：%lld
> 
> 语言限定：  
> C（clang11）, C++（clang++11）, Pascal（fpc 3.0.2）, Java（javac 1.8）, Python2（2.7.3）,  
> PHP(7.4.7), C\#(mcs5.4), ObjC(gcc 5.4), Pythen3(3.9), JavaScript Node(12.18.2), JavaScript V8(6.0.0),  
> Sqlite(3.7.9), R(4.0.3), Go(1.14.4), Ruby(2.7.1), Swift(5.3), matlab(Octave 5.2), Pypy2(pypy2.7.13),  
> Pypy3(pypy3.6.1), Rust(1.44), Scala(2.11.12), Kotlin(1.4.10), Groovy(3.0.6), TypeScript(4.1.2), Mysql(8.0)

[C]: https://renjie.blog.csdn.net/article/details/129190260
[C_]: https://blog.csdn.net/misayaaaaa/category_12036814.html
[Python]: https://blog.csdn.net/misayaaaaa/category_12111005.html
[Java]: https://blog.csdn.net/misayaaaaa/category_12111006.html
[JavaScript]: https://blog.csdn.net/misayaaaaa/category_12199270.html
[9bd3845cf20c4a8f8420d420cf885ef4.jpeg]: https://img-blog.csdnimg.cn/9bd3845cf20c4a8f8420d420cf885ef4.jpeg
[leetcode40]: https://leetcode.cn/problems/combination-sum-ii/solution/