acwing::acwing788 命名空间参考

1. 逆序对的数量

更多...

函数
int	main (istream &cin, ostream &cout)
void	ms (vector< int > &arr, int l, int r, int *ans)
void	ms (vector< int > &vec, int l, int r)
	TEST (acwing788, case1)
	TEST (acwing788, case2)

详细描述

1. 逆序对的数量

函数说明

main()

int acwing::acwing788::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing.cpp 第 6364 行定义.

                                              {
            int n;
            cin >> n;
            vector<int> vec(n);
            for(int i = 0; i < n; i++) {
                cin >> vec[i];
            }
            int ans = 0;
            ms(vec, 0, n - 1, &ans);
            cout << ans;
            return 0;
        }

引用了 ms() , 以及 pat::a::a7_2::vec.

被这些函数引用 TEST().

ms() [1/2]

void acwing::acwing788::ms	(	vector< int > &	arr,
		int	l,
		int	r,
		int *	ans
	)

在文件 acwing.cpp 第 6334 行定义.

                                                          {
            if(l >= r) {
                return;
            }
            const int m = l + r >> 1;
            ms(arr, l, m, ans);
            ms(arr, m + 1, r, ans);
            int i = l;
            int j = m + 1;
            int p = 0;
            vector<int> tmp(r - l + 1);
            while(i <= m && j <= r) {
                if(arr[i] <= arr[j]) {
                    tmp[p++] = arr[i++];
                } else {
                    tmp[p++] = arr[j++];
                    *ans += m - i + 1;
                }
            }
            while(i <= m) {
                tmp[p++] = arr[i++];
            }
            while(j <= r) {
                tmp[p++] = arr[j++];
            }
            for(int i = 0; i < p; i++) {
                arr[l + i] = tmp[i];
            }
        }

引用了 ms().

被这些函数引用 main(), acwing::acwing1875::main(), acwing::acwing1726::main(), luogu::P1603::main(), leetcode::sliding_window_maximum::Solution::maxSlidingWindow() , 以及 ms().

ms() [2/2]

void acwing::acwing788::ms	(	vector< int > &	vec,
		int	l,
		int	r
	)

TEST() [1/2]

acwing::acwing788::TEST	(	acwing788	,
		case1
	)

在文件 acwing_test.cpp 第 2979 行定义.

                               {
            istringstream in("6\n"
                             "2 3 4 5 6 1");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("5", ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing788::TEST	(	acwing788	,
		case2
	)

在文件 acwing_test.cpp 第 2988 行定义.

                               {
            istringstream in("10\n"
                             "88 71 16 2 72 38 94 50 72 67");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("21", ans);
        }

引用了 main().