将代码处理优化并加速到< = 1秒(每个测试用例) [英] Optimize and speed up processing of code to <=1sec (per test case)

问题描述

有关优化以下代码以使其运行更快的任何帮助.

any help with optimizing following code to make it run faster.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class gfg
{
public:
bool satisfiable(std::vector<int> a, std::vector<int> b) {
  while (!a.empty()) {
    std::sort(b.begin(), b.end(), std::greater<int>());
    int k = a.back();
    a.pop_back();
    if (k > b.size()) return false;
    if (k == 0) continue;
    if (b[k - 1] == 0) return false;
    for (int i = 0; i < k; i++)
      b[i]--;
  }
  for (std::vector<int>::iterator i = b.begin(); i != b.end(); i++)
    if (*i != 0)
      return false;
  return true;
}

};


int main()
{
    gfg g;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int r,c,n,cnt=0;
    cin >> n;
    while(cnt<n){
        cnt++;
    cin >> r >> c;
    int x;
      vector<int> a;
      vector<int> b;
    for(int i=0;i<r;i++){
            cin >> x;
          a.push_back(x);
    }

    for(int j=0;j<c;j++){
          cin >> x;
          b.push_back(x);
    }



    if(g.satisfiable(a,b)) cout << "YES\n";
    else cout << "NO\n";
    }

    return 0;
}

预期:每个测试用例平均处理时间为1s或更短实际:每个测试用例平均处理时间为2s至2.5s

我尝试过的事情:

Expected : Average 1s or less processing time per test case Actual : Average 2s to 2.5s processing time per test case

What I have tried:

Tried making function inline, tried cin.TIE(NULL), tried ios_base::sync_with_stdio(false);

推荐答案

一些简单的想法:

在gfg::satisfiable()中，向量 b 不会重新排序，因此您不必每次都通过while循环进行排序.您可以递减 b 的 0..k 元素，但这不会改变排序顺序.

push_back()检查向量的当前分配，并可能每次都重新分配.预分配向量，并使用直接元素访问将减少设置向量所花费的时间:

Some quick thoughts:

In gfg::satisfiable(), vector b doesn''t get re-ordered, so you don''t need to sort each time through the while loop. You do decrement elemnts 0..k elements of b, but that won''t change the sort order.

push_back() checks the current allocation of the vector and possibly re-allocates each time. Pre allocating the vector, and using direct element access will reduce the time taken to set up the vector:

vector<int> a(r);
for(int i = 0; i < r; ++i)
    cin >> a[i];

如果输入的数量很大，这将有很大帮助；

如果可能，一次性读取整个输入文件，然后使用字符串处理对其进行解析.输入格式可能非常简单，因此应该可以编写不使用(可能很慢)iostream工具的解析器.

如果您无法一次性读取整个输入文件，则可以使用getline()读取矢量的部分或全部元素，然后将其解析出来.

This will help greatly if the number of inputs is large;

If possible read the entire input file in one go, and then use string processing to parse it. The input format is probably fairly simple, so it should be possible to write a parser that doesn''t use the (possibly slow) iostream facility.

If you can''t read the entire input file in one go, maybe you can use getline() to read some, or all, of the elements of the vector, then parse them out.

这篇关于将代码处理优化并加速到< = 1秒(每个测试用例)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！