admin管理员组

文章数量:1432187

I am doing the Kattis Problem Akcija

Problem Statement

A bookstore offers a promotion where, for every three books purchased, the cheapest book in the group is free. Customers can group books strategically to minimize the total cost. The task is to calculate the minimum price a customer has to pay given the prices of the books. Each group can have between 1 and 3 books.

Bounded conditions

The first line of input contains the integer N (1<N<100 000), the number of books the customer bought. Each of the following N lines contains a single integer C_i (1<C_i<100 000), the price of each book.

My question

My idea is to sort the price in decreasing order first and then always add the first two prices in the group of 3 to my sum price. I think this idea is somewhat correct, but the algorithm I use to sort an is Bubble sort, which is O(N^2). Seems that this will cause Time Limit Exceed.

I am not sure whether O(N^2) sorting algorithm is suitable or not in this question. Can someoen help me. My code is written in C. Assume that the not-standard input/output functions work fine.

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);
}

I tried the O(N^2) sorting algorithm, but got TLE. Don't know if the problem lies in the efficiency of the sorting algorithm or somewhere else.

I am doing the Kattis Problem Akcija

Problem Statement

A bookstore offers a promotion where, for every three books purchased, the cheapest book in the group is free. Customers can group books strategically to minimize the total cost. The task is to calculate the minimum price a customer has to pay given the prices of the books. Each group can have between 1 and 3 books.

Bounded conditions

The first line of input contains the integer N (1<N<100 000), the number of books the customer bought. Each of the following N lines contains a single integer C_i (1<C_i<100 000), the price of each book.

My question

My idea is to sort the price in decreasing order first and then always add the first two prices in the group of 3 to my sum price. I think this idea is somewhat correct, but the algorithm I use to sort an is Bubble sort, which is O(N^2). Seems that this will cause Time Limit Exceed.

I am not sure whether O(N^2) sorting algorithm is suitable or not in this question. Can someoen help me. My code is written in C. Assume that the not-standard input/output functions work fine.

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);
}

I tried the O(N^2) sorting algorithm, but got TLE. Don't know if the problem lies in the efficiency of the sorting algorithm or somewhere else.

• c
• algorithm
• sorting

Share Improve this question Follow edited Nov 23, 2024 at 13:07 ggorlen 58.1k88 gold badges115115 silver badges157157 bronze badges asked Nov 19, 2024 at 7:04 mendax1234mendax1234 1333 bronze badges 3

• 1 Hello, welcome to the StackOverflow. What kind of help you expect here? You expect someone just says "try the quicksort" or you expect someone does quicksort (or yet another) here for you? Have you even tried another sorting algorithm? What was the outcome? – Wiktor Zychla Commented Nov 19, 2024 at 7:13
• Thanks! I would like someone to do a quicker sort since the fastest sorting algorithm I have learned now is O(n^2). I guess merge sort will be faster. But I don't know whether the problem lies with the efficiency of sorting or somewhere else. Thank you! – mendax1234 Commented Nov 19, 2024 at 7:15
• Just a note: qsort() (in the Standard Library) does not necessarily implement the "quick sort" algorithm. It'll (probably) be a "n log(n)" algorithm though (no respectable library will chose a worse algorithm). – pmg Commented Nov 23, 2024 at 13:31

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

I agree the O(N^2) algorithm is main reason of TLE. You get at most 100000 numbers in range 0..100000, it could be solved using any O(N log N) algorithm such as Heapsort or Mergesort, or even using linear-time algorithm such as Countingsort or Radixsort.

I am certain that test data in informatics contests are designed the way that forces solvers to use the algorithm with best possible asymptotic complexity.

本文标签： cKattis Problem AkcijaO(N2) sorting will cause Time Limit ExceedStack Overflow