Đổi chỗ các phần tử trong mảng để được số lớn nhất bằng C/C++

Đổi chỗ các phần tử trong mảng để được số lớn nhất bằng C/C++

Bài toán:

Trong một chương trình truyền hình, người chơi có cơ hội nhận được một số tiền thưởng. Số tiền được ghi lên các card (bảng). Người chơi phải đổi chỗ 2 card bất kỳ theo một số lần quy định cho trước để được số tiền lớn nhất có thể.

Ví dụ: Có 5 card sau: 3, 2, 8, 8, 8 và người chơi phải đổi chỗ 2 lần cho mỗi card bất kỳ để được một số lớn hơn. Số tiền đó tương đương với số tiền thưởng mà người chơi có thể nhận được.

Người chơi có thể đổi chỗ như sau:

  • Trước khi đổi: 3 2 8 8 8
  • Đổi chỗ lần 1: Đổi chỗ card có giá trị 3 cho card có giá trị 8 ta được: 8 2 8 3 8.
  • Đổi chỗ lần 2: Đổi chỗ card có giá trị 2 cho card có giá trị 8 ta được: 8 8 8 3 2.

Vậy sau 2 lần đổi chỗ số tiền thưởng tối đa mà người chơi có thể nhận được là : $88832.

Chú ý rằng: Người chơi phải thực hiện đổi chỗ các card theo số lần cho trước.

Ví dụ: Chương trình đưa ra 2 card : 9 4 , và người chơi phải đổi chỗ 1 lần.

Khi đó người chơi phải thực hiện đổi chỗ ít nhất 1 lần. Ta được 4 9.

Vậy số tiền mà người chơi có thể nhân được là $49.

Yêu cầu: Hãy tìm cách đổi chỗ các card để được số tiền thưởng lớn nhất.

[Input]

Dòng đầu ghi số lượng test case. Các dòng phía sau ghi danh sách card và số lần được phép đổi.

[Output]

Trên mỗi dòng in ra #C và số tiền lớn nhất mà người chơi có thể nhận được. Trong đó #C và số tiền được ngăn cách bởi một khoảng trắng.

[I/O Example]

Input.

10 // số lượng test case.
431159 7 // danh sách card (431159) và số lần đổi (3)
2737 1
757148 1
78466 2
32888 2
777770 5
436659 2
431159 7
112233 3
456789 10

Output

#1 954311
#2 7732
#3 857147
#4 87664
#5 88832
#6 777707
#7 966453
#8 954311
#9 332211
#10 987654

[Thuật toán]

  1. Với một mảng các chữ số a1,a2,a3,....an (đại diện cho danh sách card). Nếu ta đổi chỗ ai với aj ( j > i và aj > ai) thì ta được một số lớn hơn. 
  2. Từ trái qua phải tại vị trí i bất kỳ nếu tại vị trí k ( k > i) mà ak là số lớn nhất nằm bên phải của ai và ak >= ai thì ta sẽ đổi chỗ 2 số đó cho nhau.
  3. Nếu đi từ trái qua phải mà không có vị trí nào thỏa mãn để đổi chỗ thì ta sẽ đổi chỗ 2 vị trí cuối.

Ví dụ: Với 2 lần đổi hãy đổi chỗ các card  3 2 8 8 8 để được số lớn nhất.

  1. Đi từ trái qua phải, xét các vị trí từ 1 đến 5. Gặp số 3 (vị trí 1), trong các số bên phải 3 số lớn nhất tận tùng bên phải là số 8 (vị trí 5). Ta đổi chỗ số ở vị trí 1 với vị trí 5, ta được 8 2 8 8 3.
  2. Lặp lại bước 1. Gặp số 2 (vị trí 2), trong các số bên phải số 2 số lớn nhất tận cùng bên phải là số 8 (vị trí 4). Ta đổi chỗ số ở vị trí 2 với vị trí 4, ta được 8 8 8 2 3.
  3. Ta nhận thấy trong các các số được đổi sang bên phải số 2 (đổi sang vị trí 4) số 3 (đổi sang vị trí 5). Vì 2 số này có thể được đổi cho nhau mà không bị tính là mất thêm 1 bước đổi nên ta sắp xếp lại 2 số này theo thứ tự giảm dần được 3 > 2. Vậy vị trí 4 sẽ điền 3 và vị trí 5 sẽ điền 2.

Vậy ta đã mất 2 lần đổi như sau : Đổi số 3 (vị trí 1) cho số 8 (vị trí 5) và đổi số 2 (vị trí 2) cho số 8 (vị trí 4) được số  8 8 8 3 2. đây là số lớn nhất sau 2 lân đổi.

Chương trình cài đặt:

#include<iostream>

using namespace std;

int main(){

 freopen("BIGGESTPRIZE.INP", "r", stdin);

 freopen("BIGGESTPRIZE.OUT", "w", stdout);

 char cards[7];

 char swapsCards[7];

 int cardNo;

 int swapNum;

 int theGreatestNumberIndex;

 for (int t = 1; t <= 10; t++){

  for (int i = 0; i<6; i++){

   swapsCards[i] = '0';

  }

  cin >> cards >> swapNum;

  for (int i = 0; i <= 6; i++){

   if (cards[i] == '\0'){

    cardNo = i; break;

   }

  }

  while (swapNum > 0){

   bool isHas = false;

   int i;

   for (i = 0; i<cardNo - 1; i++){

    theGreatestNumberIndex = i + 1;

    for (int j = i + 1; j<cardNo; j++){

     if (cards[i]<cards[j] && cards[j] >= cards[theGreatestNumberIndex]){

      theGreatestNumberIndex = j;

      isHas = true;

     }

    }

    if (isHas){

     char temp = cards[i];

     cards[i] = cards[theGreatestNumberIndex];

     cards[theGreatestNumberIndex] = temp;

     swapsCards[theGreatestNumberIndex] = temp;

     break;

    }

   }

   if (!isHas){

    char temp = cards[cardNo - 1];

    cards[cardNo - 1] = cards[cardNo - 2];

    cards[cardNo - 2] = temp;

   }

   swapNum--;

  }


  for (int i = 0; i<cardNo; i++){

   for (int j = i + 1; j<cardNo; j++){

    if (swapsCards[i] != '0' && swapsCards[j] != '0' && swapsCards[i] < swapsCards[j]){

     char temp = swapsCards[i];

     swapsCards[i] = swapsCards[j];

     swapsCards[j] = temp;

    }

   }

  }

  for (int i = 0; i<cardNo; i++){

   if (swapsCards[i] != '0'){

    cards[i] = swapsCards[i];

   }

  }

  cout << "#" << t << " " << cards << endl;


 }

 return 0;


}

 

Bạn thấy bài viết này như thế nào?: 
Average: 8 (1 vote)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Cách làm Drupal to Ember without Saving năm 2016

Cách làm Drupal to Ember without Saving năm 2016

Running headless Drupal with a separate javascript framework on the front-end can provide amazing user experiences and easy theming

6 resources giúp bạn start a new Drupalcamp

6 resources giúp bạn start a new Drupalcamp

Getting a new regional Drupalcamp up and running appears daunting at first, but the support of the Drupal Community helps provide a giant head start. While helping the Louisiana Drupal Users Group

AVG chính thức phát sóng

AVG chính thức phát sóng

Sau hơn một năm phát sóng thử nghiệm, hệ thống truyền dẫn phát sóng truyền hình kỹ thuật số đa kênh của Công ty cổ phần Nghe nhìn toàn cầu (AVG) chính thức đi vào hoạt động từ ngày 11/11/2011.