codeforce E - Binary Inversions题解

题目：

给你一个01串，现在你可以（或者不用）选取其中一个元素进行一次反转操作0-1，1-0；从而使得串中的逆序对个数最多。

题目链接：codeforce origin problem

思路：

1. 如何统计逆序对的个数？

从后向前扫描，定义zero，记录0的个数，如果遇到1，则逆序对增加的个数就等于的此时zero。

点击查看代码

vector<int>a;

ll f(decltype(a)& d)

{

	ll zero = 0, sum = 0;

	rfor(i, d.size() - 1, 0)

	{

		//cout << d[i] << " ";

		if ( d[i] == 0 )

			zero++;

		else sum += zero;

	}

	return sum;

}

2.如何进行一次反转使得逆序对个数最多？

我们考虑0-1反转，让逆序对数量更多，则应该让下标最小的0filp为1，这样子，逆序对个数最多。
我们考虑1-0反转，让逆序对数量更多，则应该让下标最小的1filp为0，这样子，逆序对个数最多。

AC代码

//注意事项：记得开longlong，避免溢出

// 其次，不用经过反转01，可能已经是最大的了，需要先做记录

vector<int>a;

ll f(decltype(a)& d)

{

	ll zero = 0, sum = 0;

	rfor(i, d.size() - 1, 0)

	{

		//cout << d[i] << " ";

		if ( d[i] == 0 )

			zero++;

		else sum += zero;

	}

	return sum;

}

void solve()

{

	ll n;

	cin >> n;

	a.resize(n);

	ifor(i, 0, n - 1)

	{

		cin >> a[i];

	}

    ll  res;

	res = f(a);

	ifor(i, 0, n - 1)

	{

		if ( a[i] == 0 )

		{

			a[i] = 1;

			ll s1 = f(a);

			res = max(s1, res);

			a[i] = 0;

			break;

		}

	}

	rfor(i, n-1, 0)

	{

		if ( a[i] == 1 )

		{

			a[i] = 0;

			ll s1 = f(a);

			res = max(s1, res);

			a[i] = 1;

			break;

		}

	}

	cout << res<<endl;

	a.clear();

}

int main(int args, char** argv)

{

	/*ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cin.tie(nullptr);*/

	long t;

	cin >> t;

	while ( t-- )

	{

		solve();

	}

	return 0;

}

巴特西

codeforce E - Binary Inversions题解

题目：

思路：

1. 如何统计逆序对的个数？

2.如何进行一次反转使得逆序对个数最多？

AC代码

最新文章

热门文章