1035 插入与归并更多...

函数
int	main (istream &cin, ostream &cout)

	TEST (b1035, case1)

	TEST (b1035, case2)

详细描述

1035 插入与归并

函数说明

◆ main()

int pat::b::b1035::main	(	istream &	cin,
		ostream &	cout )

在文件 pat.cpp 第 1119 行定义.

                                                  {
                int n;
                cin >> n;
                vector<int> vec1(n);
                vector<int> vec2(n);
                for(int i = 0; i < n; i++) {
                    cin >> vec1[i];
                }
                for(int i = 0; i < n; i++) {
                    cin >> vec2[i];
                }
                int i = n - 1;
                for(; i >= 0 && vec1[i] == vec2[i]; --i) {}
                vector<int> sorted_vec = vec1;
                sort(sorted_vec.begin(), sorted_vec.begin() + i + 1);
                bool insertion = true;
                for(int j = 0; j <= i; j++) {
                    if(sorted_vec[j] != vec2[j]) {
                        insertion = false;
                        break;
                    }
                }
                if(insertion) {
                    //插入排序
                    cout << "Insertion Sort" << endl;
                    int j = n - 1;
                    for(; j >= 0; --j) {
                        vector vec1_cpy = vec1;
                        sort(vec1_cpy.begin(), vec1_cpy.begin() + j);
                        if(vec1_cpy == vec2) {
                            break;
                        }
                    }
                    sort(vec1.begin(), vec1.begin() + j + 1);
                    for(int k = 0; k < n; k++) {
                        cout << vec1[k];
                        if(k != n - 1) {
                            cout << ' ';
                        }
                    }
                    return 0;
                }
                //归并排序
                cout << "Merge Sort" << endl;
                int factor = 1;
                bool flag  = false;
                while(true) {
                    factor *= 2;
                    int j = 0;
                    for(; (j + 1) * factor <= n; j++) {
                        sort(vec1.begin() + j * factor, vec1.begin() + (j + 1) * factor);
                    }
                    if(j * factor < n) {
                        sort(vec1.begin() + j * factor, vec1.end());
                    }
                    if(flag) {
                        for(int k = 0; k < n; k++) {
                            cout << vec1[k];
                            if(k != n - 1) {
                                cout << ' ';
                            }
                        }
                        return 0;
                    }
                    if(vec1 == vec2) {
                        flag = true;
                    }
                }
            }

被这些函数引用 TEST() , 以及 TEST().

◆ TEST() [1/2]

pat::b::b1035::TEST	(	b1035	,
		case1	)

在文件 pat_test.cpp 第 526 行定义.

                               {
                istringstream in("10\n"
                                 "3 1 2 8 7 5 9 4 6 0\n"
                                 "1 2 3 7 8 5 9 4 6 0");
                auto out = ostringstream();
                main(in, out);
                const auto ans = out.str();
                ASSERT_EQ("Insertion Sort\n"
                          "1 2 3 5 7 8 9 4 6 0",
                          out.str());
            }

引用了 main().

◆ TEST() [2/2]

pat::b::b1035::TEST	(	b1035	,
		case2	)

在文件 pat_test.cpp 第 538 行定义.

                               {
                istringstream in("10\n"
                                 "3 1 2 8 7 5 9 4 0 6\n"
                                 "1 3 2 8 5 7 4 9 0 6");
                auto out = ostringstream();
                main(in, out);
                const auto ans = out.str();
                ASSERT_EQ("Merge Sort\n"
                          "1 2 3 8 4 5 7 9 0 6",
                          out.str());
            }

引用了 main().