主页 / 问题 / 1599998
Accepted
Egor arestovitsch
Asked:2024-11-17 01:47:04 +0000 UTC2024-11-17 01:47:04 +0000 UTC

如何解决问题 82，acmp.ru

  • 772

这是问题陈述：

（时间：1 秒。内存：64 MB）

给定两个无序整数集（可能有重复）。按升序打印两组中出现的所有数字，不要重复。输入数据

输入文件 INPUT.TXT 的第一行包含两个空格分隔的整数 N 和 M (1 ≤ N, M ≤ 300,000) — 分别是第一组和第二组的元素数量。第二行包含第一组的 N 个数字，以空格分隔。第三行包含第二组的 M 个数字，以空格分隔。每个数字都在 0 到 105 之间。 输出

在输出文件 OUTPUT.TXT 中，您需要按升序写入，而不重复第一组和第二组中包含的所有数字。数字之间用一个空格分隔。如果没有这样的数字，则输出文件应保持为空。

您可以使用 cin 和 cout 流

我已经尝试了几种解决方案，例如：像“按计数排序”

进一步使用集合

并使用 unordered_set

最后，使用排序

所有解决方案在第十次测试或第十一次测试时都失败，结论是：超出时间限制因此，没有足够的时间，有人可以建议更快的方法吗？我使用的编译器：MINGW GNU C++ 14.2.0

最快的代码是：

#include <iostream>
#include <vector>
  
using namespace std;
  
int main()
{
    int n,m, t;
    scanf("%i",&n);
    scanf("%i",&m);
    vector<int> a;
    vector<int> b;
    vector<int> c(1000000);
    for(int i = 0; i < n; ++i){
        scanf("%i",&t);
        a.push_back(t);
    }
    for(int i = 0; i < m; ++i){
        scanf("%i",&t);
        b.push_back(t);
    }
    for(int i = 0; i < a.size(); ++i)
        c[a[i]] = 1;
    for(int i = 0; i < b.size(); ++i)
        if(c[b[i]] == 1)
            c[b[i]] = 2;
    for(int i = 0; i < c.size(); ++i){
        if(c[i] == 2)
            printf("%i", i);
        printf(" ");
    }
    return 0;
}

11号测试1.25秒

c++

1 个回答

  1. Best Answer

    那么提示清楚了吗？

    #include <iostream>
#include <fstream>

using namespace std;

unsigned char a[100001], b[100001];

int main(int argc, char * argv[])
{
    ifstream in("input.txt");
    int N, M;
    in >> N >> M;
    for(int d, i = 0; i < N; ++i) { in >> d; a[d] = 1; }
    for(int d, i = 0; i < M; ++i) { in >> d; b[d] = 1; }
    ofstream out("output.txt");
    for(int i = 0; i < 100001; ++i)
    {
        if (a[i] & b[i]) out << i << " ";
    }
}
    • 2

相关问题