首页 > 代码库 > 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 (有序序列和三角形的关系)