pat::a::a7_2 命名空间参考

7-2 The Second Run of Quicksort 更多...

函数
bool	isFirstRun (int start, int end)
int	main (istream &cin, ostream &cout)
	TEST (a7_2, case1)

变量
int	lmax [100010]
int	lmax2 [100010]
int	rmin [100010]
int	rmin2 [100010]
int	vec [100010]

详细描述

7-2 The Second Run of Quicksort

函数说明

isFirstRun()

bool pat::a::a7_2::isFirstRun	(	int	start,
		int	end )

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

                                                {
                if(start >= end) {
                    return true;
                }
                lmax2[start] = vec[start];
                rmin2[end]   = vec[end];
                for(int i = start + 1; i <= end; i++) {
                    lmax2[i] = max(vec[i], lmax2[i - 1]);
                }
                for(int i = end - 1; i >= start; i--) {
                    rmin2[i] = min(vec[i], rmin2[i + 1]);
                }
                for(int i = start; i <= end; i++) {
                    if(vec[i] >= lmax2[i] && vec[i] <= rmin2[i]) {
                        return true;
                    }
                }
                return false;
            }

引用了 lmax2, rmin2 , 以及 vec.

被这些函数引用 main().

main()

int pat::a::a7_2::main	(	istream &	cin,
		ostream &	cout )

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

                                                  {
                int k;
                cin >> k;
                while(k-- != 0) {
                    int n;
                    cin >> n;
                    for(int i = 0; i < n; i++) {
                        cin >> vec[i];
                    }
                    bool ok     = false;
                    lmax[0]     = vec[0];
                    rmin[n - 1] = vec[n - 1];
                    for(int i = 1; i < n; i++) {
                        lmax[i] = max(vec[i], lmax[i - 1]);
                    }
                    for(int i = n - 2; i >= 0; i--) {
                        rmin[i] = min(vec[i], rmin[i + 1]);
                    }
                    for(int i = 0; i < n; i++) {
                        if(vec[i] >= lmax[i] && vec[i] <= rmin[i]) {
                            if(isFirstRun(0, i - 1) && isFirstRun(i + 1, n - 1)) {
                                ok = true;
                                break;
                            }
                        }
                    }
                    if(ok) {
                        cout << "Yes" << endl;
                    } else {
                        cout << "No" << endl;
                    }
                }
                return 0;
            }

引用了 isFirstRun(), lmax, rmin , 以及 vec.

被这些函数引用 TEST().

TEST()

pat::a::a7_2::TEST	(	a7_2	,
		case1	)

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

                              {
                istringstream in("4\n"
                                 "8\n"
                                 "5 2 16 12 28 60 32 72\n"
                                 "8\n"
                                 "2 16 5 28 12 60 32 72\n"
                                 "8\n"
                                 "2 12 16 5 28 32 72 60\n"
                                 "8\n"
                                 "5 2 12 28 16 32 72 60");
                auto out = ostringstream();
                main(in, out);
                ASSERT_EQ("Yes\n"
                          "Yes\n"
                          "Yes\n"
                          "No\n",
                          out.str());
            }

引用了 main().

变量说明

lmax

int pat::a::a7_2::lmax[100010]

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

被这些函数引用 main().

lmax2

int pat::a::a7_2::lmax2[100010]

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

被这些函数引用 isFirstRun().

rmin

int pat::a::a7_2::rmin[100010]

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

被这些函数引用 main().

rmin2

int pat::a::a7_2::rmin2[100010]

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

被这些函数引用 isFirstRun().

vec

int pat::a::a7_2::vec[100010]

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

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