求解HackerRank“Small Triangles, Large Triangles”问题输出不符

我在HackerRank上解决“小三角形、大三角形”问题，需求是：给定n个三角形的三边a、b、c，按面积从小到大的顺序输出这些三角形的三边（题目保证所有面积互不相同）。我写了C语言代码，但运行后实际输出和预期输出不一致，求帮忙排查问题。

问题详情：

给定n个三角形的三边a、b、c，按面积从小到大的顺序输出这些三角形的三边，题目保证所有面积互不相同。

我的代码 #

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle
{
    int a;
    int b;
    int c;
};

struct temp_tri
{
    int a;
    int b;
    int c;
};

typedef struct triangle triangle;
void sort_by_area(triangle* tr, int n)
{
       int i, j, min;
       struct temp_tri tr_temp[100];
       double p[101], s[101], area[100];
       for (i=0; i<n; i++)
       {
            p[i] = (tr[i].a + tr[i].b + tr[i].c)*(0.5);
            s[i] = sqrt(p[i]*(p[i]-tr[i].a)*(p[i]-tr[i].b)*(p[i]-tr[i].c));
            area[i] = s[i];    
       }
       //To check whether areas are calculated correctly or not
       /*for (i=0; i<n; i++)
       {
          printf("%d %d %d :- %lf\n", tr[i].a, tr[i].b, tr[i].c, area[i]);
       }*/
       for (i=0; i<n; i++)
       {
          for (j=i+1; j<n; j++)
          {
              if (area[i] > area[j])
              {
                  tr_temp[i].a = tr[i].a;
                  tr[i].a = tr[j].a;
                  tr[j].a = tr_temp[i].a;
                  
                  tr_temp[i].b = tr[i].b;
                  tr[i].b = tr[j].b;
                  tr[j].b = tr_temp[i].b;

                  tr_temp[i].c = tr[i].c;
                  tr[i].c = tr[j].c;
                  tr[j].c = tr_temp[i].c;
              }
          }
       }
}     

int main()
{
    int n;
    printf("Enter no of triangles:- \n");
    scanf("%d", &n);
    triangle *tr = malloc(n * sizeof(triangle));
    printf("Enter a, b, c:- \n");
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);
    printf("\n");
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
    }
    return 0;
}

输出对比 #

当n=10时：

实际输出 #

26 49 35
67 67 19
41 34 22
48 42 45
33 33 49
61 58 59
3 57 55 
23 43 35
63 46 45
23 12 27 

预期输出 #

3 57 55
23 12 27
41 34 22
23 43 35
26 49 35
33 33 49
67 67 19
48 42 45
63 46 45
61 58 59

问题根源与修正方案 #

问题根源 #

排序逻辑存在致命错误：交换三角形结构体的边时，没有同步更新对应的area数组元素。

area数组是基于初始的tr数组计算的，当你交换了tr[i]和tr[j]的内容后，area[i]和area[j]仍然保留着交换前的面积值。后续循环比较时，用的是错误的面积对应关系，导致排序完全混乱。

修正后的sort_by_area函数 #

void sort_by_area(triangle* tr, int n)
{
       int i, j;
       // 直接用已有的triangle结构体作为临时变量，减少冗余
       triangle tr_temp;
       double p, s, area[100];
       for (i=0; i<n; i++)
       {
            p = (tr[i].a + tr[i].b + tr[i].c) * 0.5;
            s = sqrt(p*(p-tr[i].a)*(p-tr[i].b)*(p-tr[i].c));
            area[i] = s;    
       }
       for (i=0; i<n; i++)
       {
          for (j=i+1; j<n; j++)
          {
              if (area[i] > area[j])
              {
                  // 交换三角形结构体
                  tr_temp = tr[i];
                  tr[i] = tr[j];
                  tr[j] = tr_temp;
                  
                  // 同步交换对应的面积值，保证对应关系正确
                  double area_temp = area[i];
                  area[i] = area[j];
                  area[j] = area_temp;
              }
          }
       }
}

额外优化建议 #

1. 无需单独定义temp_tri结构体，直接使用已有的triangle结构体作为临时变量即可，简化代码。
2. p和s无需定义为数组，每次循环计算单个三角形的半周长和面积即可，节省内存空间。

内容的提问来源于stack exchange，提问作者CKJ_1630