首页 > 代码库 > UVALive 7077 Little Zu Chongzhi's Triangles (有序序列和三角形的关系)
UVALive 7077 Little Zu Chongzhi's Triangles (有序序列和三角形的关系)
这个题……我上来就给读错了，我以为最后是一个三角形，一条边可以由多个小棒组成，所以想到了状态压缩各种各样的东西，最后成功了……结果发现样例过不了，三条黑线就在我的脑袋上挂着，改正了以后我发现N非常小，想到了回溯每个棍的分组，最多分5组，结果发现超时了……最大是5^12 = 244,140,625，厉害呢……
后来想贪心，首先想暴力出所有可能的组合，结果发现替换问题是一个难题……最后T T ，我就断片了。。
等看了别人的办法以后，我才发现我忽视了三角形的特性，和把数据排序以后的特点。 如果数据从大到小排序为 a,b,c,d,e...会发现这样一个特点，a+b>c，a+c>b，这样一来组合成三角形的唯一条件就是b+c>a，同时也发现是a以后的任意两个数的和都不会大于b+c，所以只要b+c不行，后面的都不可以。如果b+c可以，那么他就是最好的选择，因为后面的任意一对都不可能组合成比a,b,c面积更大的三角形。所以这个题就很清晰了，i只能和i+1和i+2组合为三角形。也可以把这个题归为贪心，也是因为他确实具有贪心的特性，不过更多的是应用有序序列和三角形的关系。
受这个题的影响，我想起了在2016CCPC长春站做过的一道题，给出一个1-n的序列，求出最少去掉多少个数使其不能构成三角形。这样一来这个序列就是从小到大拍的，a,b,c,d,e，首先b+c>a，a+c>b，所以只要满足a+b>c就可以构成三角形，所以应该尽量避免这样的情况产生，处理方法为，去掉满足这样情况的c，为什么去c，不去a和b呢，因为要把尽量小的数留下来，最后会发现，留下的是1,2,3,5,8...的斐波那契数列。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<vector>#include<algorithm>using namespace std;#define N 13int stick[N],n;bool cmp(int a,int b){ return a > b;}bool ok(int i,int j,int k){ return stick[j]+stick[k]>stick[i];}double Get_area(int a,int b,int c){ double p = (a+b+c)/2.0; return sqrt(p*(p-a)*(p-b)*(p-c));}int main(){// freopen("I.in.cpp","r",stdin); double ans; while(~scanf("%d",&n)) { if(n == 0) break; for(int i = 0; i < n; i++) { scanf("%d",&stick[i]); } sort(stick,stick+n,cmp); ans = 0; for(int i = 0; i < n-2; i++) { if(ok(i,i+1,i+2)) { ans += Get_area(stick[i],stick[i+1],stick[i+2]); i += 2; } } printf("%.2f\n",ans); } return 0;}
UVALive 7077 Little Zu Chongzhi's Triangles (有序序列和三角形的关系)