Furinaaaa @ 2024-06-29 22:50:50
本菜鸡搞不懂归并中指针移动什么的,只能借助优先队列来解决。VS2022上输入样例弹窗报错,上洛谷想看看什么原因炸了却AC了,求问大佬为什么本地编译报错,感激不尽 报错内容: front()called on empty vector
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
#include<queue>
using namespace std ;
typedef unsigned long long U ;
U n ;
//存储每一个数
U nums[600000] ;
//记录答案
U ans = 0;
//尝试递归
U dfs(U start, U end)
{
//ans = 左堆中所有逆序对 + 右堆中所有逆序对 + 左右中的所有逆序对
//因为在左和右的比较中,先后顺序大小是必定确定的,而我们不关心内部是如何排序的
//所以可以对左右两堆排序后再进行比较,简简单单
//采用深搜
U x = 0;
//出口
if (start == end)
{
//单个,无法再分
return 0 ;
}
//其他
U divide =( start + end ) / 2 ;
//对左右两堆比较
priority_queue <U , vector<U> , greater<U> > left , right ;
//录入队列
for (U i = start; i <= divide; i++)
{
left.push(nums[i] ) ;
}
for (U i = divide + 1 ; i <= end ; i++)
{
right.push(nums[i]);
}
while ( 1 )
{
if (left.empty() )
{
break ;
}
if (right.empty())
{
break ;
}
//一旦左边的队首大于右边的队首,那么左边的所有元素都与右边队首组成逆序对
if (left.top() > right.top())
{
x += left.size() ;
//弹出右边的队首
right.pop() ;
}
//左边的队首小于等于右边的队首,则弹出左边队首,看看下一个怎么样
if (left.top() <= right.top())
{
left.pop() ;
}
}
//先计算左右两堆的
x += dfs(start, divide);
x += dfs(divide + 1, end);
return x ;
}
int main()
{
scanf ("%llu" , &n ) ;
//输入数据
for (U i = 0; i < n; i++)
{
scanf ("%llu" , &nums[i] ) ;
}
ans = dfs ( 0 , n -1 ) ;
//输出答案
printf("%llu" , ans ) ;
return 0;
}```
by 水星湖 @ 2024-06-29 23:21:48
报错不是已经告诉你了吗 @zkyqs123456
by elsc @ 2024-06-29 23:27:47
@zkyqs123456 把
if (left.top() <= right.top())
改成else就行
vs报错是因为你取了空队列堆顶, 内部top()的实现应该调用了vector.front()
by elsc @ 2024-06-29 23:33:31
顺便提一句, 你用优先队列的做法复杂度是大于线性对数的(且常数不优), 如果出题人卡时间很难过去
by Furinaaaa @ 2024-06-30 20:40:38
@Lzl_Doctor 谢谢大佬