算法设计与分析 5.2 洪尼玛的围栏

题目描述

  洪尼玛有块长度不同的木板，他想用这些木板拼成一个等边三角形的围栏，好将他的草泥马养在这个围栏里面。现在，给你这块木板的长度，洪尼玛想知道他能否拼成这个围栏？要求：块木板都得用上。

输入格式

第一行为一个正整数，表示有组测试数据。

对于每组测试数据，第一行为一个正整数，表示木板个数；第二行包含个正整数，表示每块木板的长度。

对于60%的数据，1 <= T <= 5, 3 <= n <= 5, 1 <= 木板长度 <= 100。

对于100%的数据，1 <= T <= 5, 3 <= n <= 10, 1 <= 木板长度 <= 100。

输出格式

如果能拼成围栏输出Yes，否则输出No。

样例输入

2
4
1 2 3 4
4
1 2 3 3

样例输出

No
Yes

参考代码

#include <iostream>
#include <algorithm>
#define MAX 10
/*
* n个数如果可以组成等边三角形，则边长为：n个数总和/3
* 从大到小排序，
* 遍历，如果该元素可以放进第一边，则放入，不可以则放入下一条边；
* 如果三条边都放不下，则一定无法组成等边三角形
* 如果所有元素都放入，则组成等边三角形。
*/
bool cmp(int a, int b) {return a > b;
}bool canBuild(int a[], int n, int avg) {int tri[3] = { 0 };std::sort(a, a + n, cmp);for (int j = 0; j < n; j++) {if (tri[0] + a[j] <= avg) {tri[0] += a[j];}else if (tri[1] + a[j] <= avg) {tri[1] += a[j];}else if (tri[2] + a[j] <= avg) {tri[2] += a[j];}else {return false;}}return true;
}int main()
{int T, n, a[MAX];float sum, avg;std::cin >> T;for (int i = 0; i < T; i++) {std::cin >> n;sum = 0;for (int j = 0; j < n; j++) {std::cin >> a[j];sum += a[j];}avg = sum / 3;//std::cout << sum<<" " << avg << " " << (int)avg << std::endl;if (avg != (int)avg) {std::cout << "No" << std::endl;}else {if (canBuild(a, n, (int)avg)) {std::cout << "Yes" << std::endl;}else {std::cout << "No" << std::endl;}}}
}