Problem - F - Codeforces
————
可以先练道逆序对的题:P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原理概括:(abcd当做一组降序的4个数,现在进行归并)
//merge 降序: abcd mnop
//a大或者m大: a大,比右边全大,全是逆序对 -> ans+右边剩余数目,a归
// m大,比左边全大,m没有逆序对了 -> m归,不操作ans
————
然后注意这道F题,
两人之间只会打一次招呼
我们按左节点顺序排,这样前面的左边界都包含后面的左边界
接下来看右边界,暴力看会超时。其实我们就是希望知道前面的右包含多少个后面的右
这就是逆序对(此时只看右区间就好)文章来源:https://www.toymoban.com/news/detail-819237.html
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模板网!