超级码力在线编程大赛初赛第1场-2-正三角形拼接题解
目录
- 题目描述
- 示例
- 输入
- 输出
- 说明
- 题解
- 代码
题目描述
给出n根木棍，每次切割可以将1根木棍切成2段。 请计算出最少切割几次，可以从所有木棍中选出3根，组成一个正三角形。
一开始的木棍根数为n，3<=n<=1000。 所有木棍的长度为一个整型数组lengths[]，1<=lengths[i]<=1e9。切割必须要将木棍分成2根整数长度的木棍，而且总长度要和原木棍相等。题目数据保证有解。
示例
输入
[2,3,7,5]
输出
2
说明
可以从长为7的木棍中，切出2根长为3的木棍，那么木棍的长度应该为[2,3,1,3,3,5]，可以拼出边长为3的正三角形。
题解
这道题目其实选择了一个比较复杂的场景，但问了一个很简单的问题。如果这道题目问至少切割多少次可以拼出一个三角形，那么难度就完全不在一个量级上了。
这里问拼成正三角形，也就是问切割几次可以得到三根一样长的木棍。
入手点应该在于：原本存不存在一样长的木棍？
-
如果原本就有三根一样长的木棍，那么不用切割，切割次数为0。
-
如果原本有两根一样长的木棍，那么有可能只需要再切割一次，再得到一根这样长的木棍就可以，但也有可能无法再切出这样长的木棍，比如：1,3,3。总结起来，只要有比该长度还长的木棍，就只需要切割1次。
-
如果给的一堆木棍中不存在一样长的木棍，那么需要切割几次呢？三次吗？当然不要这么傻，最多切割两次，得到两根和最短长度一样长的木棍，就可以了！比如：1,2,3，从后两根中各切割一次，再得到两根1，不就可以了吗！但是观察到，我切一次2，不就得到了两个1了吗，所以这里只需要切割一次就行了。也就是如果存在某一根木棍是另一根木棍长度的2倍，那么只切1次就行了。
上面的情况有点多，不过按部就班地，分情况一个个讨论就行了。先对木棍按长度排序，之后遍历每一根木棍讨论每一种情况就可以了。下面是详细代码，还可以通过剪枝进行进一步简化，比如如果当前最优解为切1次，那么只需要再检查是否切0次可行就可以了，没必要再检查所有的情况。但时间复杂度不会有区别。
代码
class Solution {
public:
int makeEquilateralTriangle(vector<int> &lengths) {
sort(lengths.begin(),lengths.end());
int rs=2;
for(int i=0; i<lengths.size(); i++) {
if(lengths.size()-1-i>=2) {
//该木棍后面还有两根以上木棍
//可以通过切两次解决
rs=min(rs,2);
//如果存在两根等长，可以切一次解决
if(lengths[i+1]==lengths[i]) {
rs=min(rs,1);
}
如果存在三根等长，可以切零次解决
if(lengths[i+1]==lengths[i] &&lengths[i+2]==lengths[i]) {
rs=min(rs,0);
}
}
//再找一找有没有2倍长度关系
if(lengths.size()-1-i>=1)
for(int j=i+1; j<lengths.size(); j++) {
if(lengths[j]==2*lengths[i]) {
rs=min(rs,1);
}
}
}
return rs;
}
};