洛谷上AC,VS2022上报错,奇了怪了

P1908 逆序对

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 谢谢大佬


|