fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Struct để lưu trữ cặp giá trị a_i và b_i
  5. typedef struct {
  6.     char a;
  7.     double b;
  8. } Pair;
  9.  
  10. // Hàm so sánh để sử dụng trong qsort
  11. int compare(const void *a, const void *b) {
  12.     const Pair *pairA = (const Pair *)a;
  13.     const Pair *pairB = (const Pair *)b;
  14.     return (pairA->b - pairB->b);
  15. }
  16.  
  17. // Hàm in ra trace
  18. void printTrace(Pair *pairs, int size) {
  19.     for (int i = 0; i < size; i++) {
  20.         printf("%c ", pairs[i].a);
  21.     }
  22.     printf("\n");
  23. }
  24.  
  25. // Hàm thực hiện B1: sắp xếp dãy b_i và tương ứng sắp xếp dãy a_i
  26. void stepB1(Pair *pairs, int size) {
  27.     qsort(pairs, size, sizeof(Pair), compare);
  28. }
  29.  
  30. // Hàm thực hiện B2: lặp cho đến khi chỉ còn một phần tử trong dãy b_i
  31. void stepB2(Pair *pairs, int size) {
  32.     while (size > 1) {
  33.         // Chọn hai phần tử có giá trị nhỏ nhất
  34.         double min1 = pairs[0].b;
  35.         double min2 = pairs[1].b;
  36.         int idx1 = 0;
  37.         int idx2 = 1;
  38.         for (int i = 2; i < size; i++) {
  39.             if (pairs[i].b < min1) {
  40.                 min2 = min1;
  41.                 idx2 = idx1;
  42.                 min1 = pairs[i].b;
  43.                 idx1 = i;
  44.             } else if (pairs[i].b < min2) {
  45.                 min2 = pairs[i].b;
  46.                 idx2 = i;
  47.             }
  48.         }
  49.  
  50.         // Ghép hai phần tử chọn được thành một phần tử mới
  51.         double sum = min1 + min2;
  52.         char newA = pairs[idx1].a < pairs[idx2].a ? pairs[idx1].a : pairs[idx2].a;
  53.  
  54.         // Xóa hai phần tử đã ghép và thêm phần tử mới vào dãy
  55.         pairs[idx1] = pairs[idx2] = pairs[size - 1];
  56.         pairs[size - 2].a = newA;
  57.         pairs[size - 2].b = sum;
  58.  
  59.         // Giảm kích thước của dãy đi hai phần tử đã ghép
  60.         size--;
  61.  
  62.         // Sắp xếp lại dãy b_i để tiếp tục lặp
  63.         qsort(pairs, size, sizeof(Pair), compare);
  64.  
  65.         // In ra trace sau mỗi bước lặp
  66.         printTrace(pairs, size);
  67.     }
  68. }
  69.  
  70. int main() {
  71.     int testCases;
  72.     scanf("%d", &testCases);
  73.  
  74.     while (testCases--) {
  75.         int M;
  76.         scanf("%d", &M);
  77.  
  78.         // Tạo mảng lưu trữ các cặp giá trị a_i và b_i
  79.         Pair *pairs = (Pair *)malloc(M * sizeof(Pair));
  80.  
  81.         // Nhập dữ liệu cho mảng
  82.         for (int i = 0; i < M; i++) {
  83.             scanf(" %c", &pairs[i].a);
  84.             scanf("%lf", &pairs[i].b);
  85.         }
  86.  
  87.         // Thực hiện bước B1
  88.         stepB1(pairs, M);
  89.  
  90.         // In ra trace trước khi thực hiện bước B2
  91.         printTrace(pairs, M);
  92.  
  93.         // Thực hiện bước B2
  94.         stepB2(pairs, M);
  95.  
  96.         // Giải phóng bộ nhớ đã cấp phát cho mảng
  97.         free(pairs);
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
1
4
 a 0.15
 b 0.125
 c 0.25
 d 0.5
stdout
copy 
a b c d 
d d a 
a a 
a
https://ideone.com/ZVkpBR
language:
C (gcc 8.3)
created:
30 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!