Codeforces Round 918 (Div. 4)F题归并逆序对

这篇具有很好参考价值的文章主要介绍了Codeforces Round 918 (Div. 4)F题归并逆序对。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem - F - Codeforces

————

可以先练道逆序对的题:P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 原理概括:(abcd当做一组降序的4个数,现在进行归并)

//merge     降序:  abcd    mnop
	//a大或者m大: a大,比右边全大,全是逆序对   -> ans+右边剩余数目,a归
	//			   m大,比左边全大,m没有逆序对了 -> m归,不操作ans

————

然后注意这道F题,

两人之间只会打一次招呼

我们按左节点顺序排,这样前面的左边界都包含后面的左边界

接下来看右边界,暴力看会超时。其实我们就是希望知道前面的右包含多少个后面的右

这就是逆序对(此时只看右区间就好)

AC代码:文章来源地址https://www.toymoban.com/news/detail-819237.html

ll ans;
void merge(int left, int right, vector<vector<int>>& arr)
{
	if (left >= right)return;
	int mid = left + (right - left) / 2;
	merge(left, mid, arr);
	merge(mid + 1, right, arr);
	vector<int>tmp(right - left + 1);
	int l = left, r = mid + 1, cur = 0;
	while (l <= mid && r <= right)
	{
		if (arr[l][1] > arr[r][1])
		{
			ans += right - r + 1;//ans
			tmp[cur++] = arr[l++][1];
		}
		else
		{
			tmp[cur++] = arr[r++][1];
		}
	}
	while (l <= mid)
	{
		tmp[cur++] = arr[l++][1];
	}
	while (r <= right)
	{
		tmp[cur++] = arr[r++][1];
	}
	cur = left;
	for (int i = 0; i < tmp.size(); i++)
	{
		arr[cur + i][1] = tmp[i];
	}
}
void solve()
{
	ans = 0;
	int n; cin >> n;
	vector<vector<int>>arr(n, vector<int>(2));
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i][0] >> arr[i][1];
	}
	sort(arr.begin(), arr.end());


	merge(0,n-1,arr);
	cout << ans << endl;
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

到了这里,关于Codeforces Round 918 (Div. 4)F题归并逆序对的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(48)
  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(44)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(43)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(38)
  • Codeforces Round 894 (Div. 3)

    签到题 a数组里,大于等于前一个值的a[i]会被写到b里。直接遍历b,如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度,判断是否相等就行 对于没有重复口味的集合,能选出的方案是n*(n-1)/2 (从n个里面选2个的组合数)。二分找出需要多少不同口味的冰淇淋,

    2024年02月11日
    浏览(45)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(45)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(45)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(57)
  • Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串,问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组,问连续相邻为0的最大长度 维护一个全局最大长度res,和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(53)
  • Codeforces Round 858 (Div. 2)题解

    目录 A. Walking Master(贪心) 题面翻译 思路: 代码实现  B. Mex Master(贪心) 题面翻译: 思路: 代码实现 C. Sequence Master(数学) 题面翻译: 思路: 代码实现 YunQian is standing on an infinite plane with the Cartesian coordinate system on it. In one move, she can move to the diagonally adjacent point on the

    2023年04月08日
    浏览(79)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包