fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // Hàm thực hiện đảo ngược đoạn đầu của mảng
  8. void flip(vector<int>& arr, int k) {
  9.     reverse(arr.begin(), arr.begin() + k);
  10. }
  11.  
  12. // Hàm tìm vị trí của giá trị target trong mảng
  13. int find(const vector<int>& arr, int target) {
  14.     for (int i = 0; i < arr.size(); ++i) {
  15.         if (arr[i] == target) {
  16.             return i;
  17.         }
  18.     }
  19.     return -1; // Không tìm thấy (trường hợp này không xảy ra trong bài toán)
  20. }
  21.  
  22. // Hàm thực hiện pancake sort
  23. vector<int> pancakeSort(vector<int>& arr) {
  24.     vector<int> result;
  25.  
  26.     // Bắt đầu từ giá trị lớn nhất và giảm dần
  27.     for (int valueToSort = arr.size(); valueToSort > 0; --valueToSort) {
  28.         // Tìm vị trí của giá trị lớn nhất hiện tại
  29.         int index = find(arr, valueToSort);
  30.  
  31.         // Nếu giá trị đã ở đúng vị trí, bỏ qua
  32.         if (index == valueToSort - 1) {
  33.             continue;
  34.         }
  35.  
  36.         // Đưa giá trị về đầu mảng nếu cần
  37.         if (index != 0) {
  38.             result.push_back(index + 1); // Lưu bước lật
  39.             flip(arr, index + 1);       // Lật đoạn đầu mảng
  40.         }
  41.  
  42.         // Đưa giá trị về đúng vị trí cuối mảng
  43.         result.push_back(valueToSort); // Lưu bước lật
  44.         flip(arr, valueToSort);       // Lật đoạn chứa giá trị cần sắp xếp
  45.     }
  46.  
  47.     return result;
  48. }
  49.  
  50. // Hàm chính
  51. int main() {
  52.     int n;
  53.     cin >> n;
  54.  
  55.     vector<int> arr(n);
  56.     for (int& x : arr) {
  57.         cin >> x;
  58.     }
  59.  
  60.     vector<int> result = pancakeSort(arr);
  61.  
  62.     // In ra số bước lật
  63.     cout << "Number of flips: " << result.size() << endl;
  64.  
  65.     // In ra các bước lật
  66.     for (int flipSize : result) {
  67.         cout << flipSize << " ";
  68.     }
  69.     cout << endl;
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
5 2 3 4 1
stdout
copy 
Number of flips: 5
5 2 4 2 3
https://ideone.com/tqz4LX
language:
C++14 (gcc 8.3)
created:
8 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!