本地运行成功上传到洛谷上却WA？

Question

题目如上，本人在本地测试过程序是OK的，上传到洛谷之后却判WA，到底是哪里有问题呢？
有无朋友能够帮忙看看？

#include<iostream>
#include<vector>
#include<queue>
#include<list>
#include<functional>

using namespace std;

//比较两个pair，第一个元素是列表中的值，第二个元素是列表的迭代器
struct Compare {
    bool operator()(const pair<int, pair<list<int>::iterator, list<int>*>>& a,
        const pair<int, pair<list<int>::iterator, list<int>*>>& b) {
        return a.first > b.first; // 创建一个最小堆
    }
};

int main() {
    int N = 0;
    cin >> N;

    vector<list<int>> lists(N);
    for (auto& lst : lists) {
        int num = 0;
        while (cin >> num)
        {
            lst.push_back(num);
            if (cin.peek() == '\n')//换行则停止读取该link list
                break;
        }
    }

    priority_queue<pair<int, pair<list<int>::iterator, list<int>*>>,
        vector<pair<int, pair<list<int>::iterator, list<int>*>>>,
        Compare> pq;

    //将每个link list的第一个元素加入优先队列
    for (size_t i = 0; i < lists.size(); ++i) {
        if (!lists[i].empty()) {
            pq.emplace(lists[i].front(), make_pair(lists[i].begin(), &lists[i]));
        }
    }

    list<int> result;

    // 合并链表
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        int value = top.first;
        auto it = top.second.first;
        auto& lst = *top.second.second;
        result.push_back(value);

        if (++it != lst.end()) { // 如果不是链表的最后一个元素
            pq.emplace(*it, make_pair(it, &lst));
        }
    }

    // 输出结果
    bool first = true;
    for (int val : result) {
        if (!first) {
            cout << " ";
        }
        else {
            first = false;
        }
        cout << val;
    }
    cout << endl;

    return 0;
}

Answer 1

提示： 本回答参考 AIGC，由本人审核整理提供。若问题解决，望采纳；如仍有疑问，请评论回复。

问题分析

你在本地测试程序时是OK的，但上传到洛谷后却被判为WA（Wrong Answer）。这种情况通常是由于以下几个原因之一：

1. 输入输出格式问题：洛谷的输入输出格式可能与本地测试时的格式不同。
2. 边界条件处理不当：程序在处理边界条件时可能出现了问题。
3. 数据范围问题：题目中提到的数据范围可能没有被正确处理。
4. 编译器差异：不同编译器对代码的解析可能略有不同，导致行为不一致。

代码审查

我们先来审查一下你的代码，看看是否有潜在的问题。

代码结构

1. 输入处理：

   • 你使用了一个循环来读取每个链表的元素，直到遇到换行符为止。
   • 这种读取方式在本地测试时可能没问题，但在洛谷上可能会因为输入格式不同而出现问题。

2. 优先队列的使用：

   • 你使用了一个优先队列来合并链表，这种方式是正确的。
   • 但是，优先队列的比较函数中，你使用了 > 来创建最小堆，这是正确的。

3. 输出处理：

   • 你在输出结果时，使用了 first 变量来控制空格的输出，这种方式是正确的。

可能的问题点

1. 输入格式：

   • 洛谷的输入格式可能与本地测试时的格式不同，特别是换行符的处理。
   • 你可以尝试使用 getline 来读取每一行的输入，确保输入格式一致。

2. 边界条件：

   • 题目中提到 1 < N < 999，但你的代码中没有对 N 进行范围检查。
   • 虽然题目中提到 1 < N < 999，但你的代码中没有对 N 进行范围检查。

3. 数据范围：

   • 题目中提到每个链表的长度可能达到 100000，但你的代码中没有对链表长度进行限制。
   • 虽然题目中提到每个链表的长度可能达到 100000，但你的代码中没有对链表长度进行限制。

解决方案

1. 改进输入处理：
   • 使用 getline 来读取每一行的输入，确保输入格式一致。
   • 示例代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <functional>
#include <sstream>
using namespace std;

// 比较两个pair，第一个元素是列表中的值，第二个元素是列表的迭代器
struct Compare {
    bool operator()(const pair<int, pair<list<int>::iterator, list<int>*>>& a,
                    const pair<int, pair<list<int>::iterator, list<int>*>>& b) {
        return a.first > b.first; // 创建一个最小堆
    }
};

int main() {
    int N = 0;
    cin >> N;
    cin.ignore(); // 忽略换行符

    vector<list<int>> lists(N);
    for (auto& lst : lists) {
        string line;
        getline(cin, line);
        stringstream ss(line);
        int num;
        while (ss >> num) {
            lst.push_back(num);
        }
    }

    priority_queue<pair<int, pair<list<int>::iterator, list<int>*>>,
                   vector<pair<int, pair<list<int>::iterator, list<int>*>>>,
                   Compare> pq;
    // 将每个link list的第一个元素加入优先队列
    for (size_t i = 0; i < lists.size(); ++i) {
        if (!lists[i].empty()) {
            pq.emplace(lists[i].front(), make_pair(lists[i].begin(), &lists[i]));
        }
    }

    list<int> result;
    // 合并链表
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        int value = top.first;
        auto it = top.second.first;
        auto& lst = *top.second.second;
        result.push_back(value);
        if (++it != lst.end()) { // 如果不是链表的最后一个元素
            pq.emplace(*it, make_pair(it, &lst));
        }
    }
    // 输出结果
    bool first = true;
    for (int val : result) {
        if (!first) {
            cout << " ";
        } else {
            first = false;
        }
        cout << val;
    }
    cout << endl;
    return 0;
}

1. 边界条件检查：
   • 在读取 N 时，可以添加一个范围检查，确保 N 在 1 < N < 999 范围内。

if (N <= 1 || N >= 999) {
    cerr << "N is out of range" << endl;
    return 1;
}

1. 数据范围检查：
   • 在读取每个链表时，可以添加一个长度检查，确保每个链表的长度在合理范围内。

if (lst.size() > 100000) {
    cerr << "List length exceeds the limit" << endl;
    return 1;
}

总结

通过改进输入处理、添加边界条件检查和数据范围检查，你的代码应该能够在洛谷上正确运行。希望这些建议能帮助你解决问题。