来自 HackerRank 的 Mini-Max Sum 问题（C 语言）

Question

我已经尝试在 HackerRank 上解决这个问题

给定五个正整数，求出可以通过将五个整数中的四个恰好相加来计算的最小值和最大值。然后将各自的最小值和最大值打印为一行两个 space 分隔的长整数。

示例

arr[5] = [1,3,5,7,9]

最小总和为1+3+5+7=16，最大总和为3+5+7+9=24。函数打印

16 24

...并且 test0 和 test1 正常工作：

测试0

输入（标准输入）

1 2 3 4 5

预期输出

10 14

测试14

输入（标准输入）

7 69 2 221 8974

预期输出

299 9271

在测试用例期间，我的代码未通过 10/15 测试，例如：

测试2

输入（标准输入）

396285104 573261094 759641832 819230764 364801279

预期输出

2093989309 2548418794

测试10

输入（标准输入）

501893267 649027153 379408215 452968170 487530619

预期输出

1821800271 2091419209

这是我的代码，我哪里做错了什么？

void swap(int *p1, int *p2){
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void selectionSort(int *arr, int arr_count)
{
     int i, j, minIndex;
     for(i=0; i<arr_count;i++){
         minIndex = i;
         for(j=i+1; j<arr_count; j++){
             if(arr[j]<arr[minIndex]){
                 minIndex = j;
             }
         }
         
         swap(&arr[minIndex],&arr[i]);
     }

}
void miniMaxSum(int arr_count, int* arr) {
    
    int i;
    int max1=0, max2=0, genericSum=0;
    
    selectionSort(arr, arr_count);
    
    for(i=0; i<arr_count; i++){
        genericSum += arr[i];
    }
    max1 = genericSum - arr[0];
    max2 = genericSum - arr[arr_count-1];
    
    printf("%d %d", max2, max1);
    return;

}

可能是数据类型的问题，因为在主 arr 中初始化为 int 但也许使用 long 可能会更好...

Answer 1

void miniMaxSum(int arr_count, int* arr) {
int i;
long long int max1=0, max2=0, genericSum=0;

selectionSort(arr, arr_count);

for(i=0; i<arr_count; i++){
    genericSum += arr[i];
}
max1 = genericSum - arr[0];
max2 = genericSum - arr[arr_count-1];

printf("%lld %lld", max2, max1);
return;
}

刚刚用 'int' 替换了 'long long int' 并且在 printf 中我使用了 %lld 而不是 %d

Answer 2

如上文 Aconcagua 所述，该问题在 O(n) 时间内解决，无需使用排序例程。以下解决方案使用 Ada 编程语言。

-----------------------------------------------------------------------
--  Given five positive integers, find the minimum and maximum values
-- that can be calculated by summing exactly four of the five integers.
-- Then print the respective minimum and maximum values as a single
-- line of two space-separated long integers.
--
--  Input Format
--
--  A single line of five space-separated integers.
--
--  Constraints
--
--  Each integer is in the inclusive range .
--  Output Format
--
--  Print two space-separated long integers denoting the respective
-- minimum and maximum values that can be calculated by summing exactly
-- four of the five integers. (The output can be greater than a 32
-- bit integer.)
------------------------------------------------------------------------
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
   type Num_T is range 0 .. 10**11;
   package Nums_Io is new Ada.Text_IO.Integer_IO (Num_T);
   use Nums_Io;

   Sum : Num_T := 0;
   Max : Num_T := 0;
   Min : Num_T := Num_T'Last;
   I   : Num_T;
begin
   for x in 1 .. 5 loop
      Get (I);
      Sum := Sum + I;
      Max := Num_T'Max (Max, I);
      Min := Num_T'Min (Min, I);
   end loop;

   Put (Item => Sum - Max, Width => 1);
   Put (" ");
   Put (Item => Sum - Min, Width => 1);
   New_Line;

end Main;

题目定义题目的数据范围为0到10^11。类型 Num_T 被定义为对应于该范围。程序读入 5 个 Num_T 类型的值，对读入的值求和，计算最小值和最大值，然后打印总和减去最大值，然后打印总和减去最小值。

来自 HackerRank 的 Mini-Max Sum 问题（C 语言）

Mini-Max Sum problem from HackerRank (in C)

c

arrays

sorting

sum

minimax