我正在做 Kattis 问题Akcija

问题陈述

一家书店推出了一项促销活动，每购买三本书，该组中最便宜的一本书将免费赠送。客户可以策略性地将书籍分组，以尽量减少总成本。任务是根据书籍的价格计算客户必须支付的最低价格。每组可以有 1 到 3 本书。

有界条件

输入的第一行包含整数 N (1<N<100 000)，表示顾客购买的书籍数量。接下来的 N 行中的每一行都包含一个整数 C_i (1<C_i<100 000)，表示每本书的价格。

我的问题

我的想法是先按降序对价格进行排序，然后始终将 3 组中的前两个价格添加到我的总价格中。我认为这个想法在某种程度上是正确的，但我用来排序的算法是冒泡排序，它是 O(N^2)。似乎这会导致超出时间限制。

我不确定 O(N^2) 排序算法是否适合这个问题。有人能帮我吗？我的代码是用 C 编写的。假设非标准输入/输出函数工作正常。

void swap(long a[], long src, long tar)
{
  long temp = a[src];
  a[src] = a[tar];
  a[tar] = temp;
}

void bubble_pass(size_t last, long a[]) {
  for (size_t i = 0; i < last; i += 1) {
    if (a[i] < a[i+1]) {
      swap(a, i, i+1);
    }
  }
}

void bubble_sort(size_t n, long a[n]) {
  for (size_t last = n - 1; last > 0; last -= 1) {
    bubble_pass(last, a);
  }
}

long calc_min_price(size_t n, long a[n])
{
  size_t cur = 0;
  long price = 0;
  for (size_t i = 0; i < n; i += 1)
  {
    if (i % 3 != 2)
    {
      price += a[i];
    }
  }
  return price;
}    

int main()
{
  size_t n = cs1010_read_size_t();
  long *price = cs1010_read_long_array(n);
  if (price == NULL)
  {
    return 1;
  }
  bubble_sort(n, price);
  long min_price = calc_min_price(n, price);
  cs1010_println_long(min_price);
  free(price);
}

我尝试了 O(N^2) 排序算法，但得到了 TLE。不知道问题出在排序算法的效率上还是其他地方。