#include <iostream> #include<vector> #include<algorithm> using namespace std; class mycompare { public: bool operator()(int s1, int s2) { return s1 <s2; } }; int main() { mycompare mycompare1; int n, m, c,i; vector<int> v1, v2; cout << "作业个数为："; cin >> n; cout << "作业时间依次为：" <<endl; for (i = 0; i < n; i++) { cin >>c; v1.push_back(c); } sort(v1.begin(), v1.end(), mycompare1);//作业时间降序排序 cout <<"处理机个数为："; cin >> m; for (i = 0; i < m; i++) v2.push_back(0); for (i = 0; i <n; i++) { sort(v2.begin(), v2.end());//处理机完成作业时间升序排列 v2[0] += v1[i];//将作业分配给最先空闲的处理机，并将处理机完成作业时间加上相应作业时间 } cout <<"最短处理机时间为：" <<*v2.rbegin()<<endl; return 0; }此代码的时间复杂度和空间复杂度

这段代码的时间复杂度为 O(nlogn)，其中 n 为作业个数。这是由于代码中使用了 STL 中的 sort 函数对作业时间进行了降序排序，时间复杂度为 O(nlogn)，而后面的循环中对处理机完成作业时间进行了升序排序，时间复杂度为 O(mlogm)，m 为处理机个数，但是由于 m 远小于 n，因此可以忽略不计。接着，循环中的分配作业的操作，时间复杂度为 O(nlogm)，最坏情况下，需要将 n 个作业分配到 m 个处理机中，因此需要进行 n 次分配操作，每次操作都需要对 m 个处理机完成作业时间进行排序，时间复杂度为 O(mlogm)，因此总的时间复杂度为 O(nlogn + nlogm)。

这段代码的空间复杂度为 O(n + m)，其中 n 为作业个数，m 为处理机个数。这是由于代码中使用了 STL 中的 vector 来存储作业时间和处理机完成作业时间，因此需要分别开辟 n 和 m 个空间来存储这些数据。此外，由于只使用了常数个变量，因此不会对空间复杂度产生影响。

相关问题

#include <iostream> #include <cstdio> #include <vector> #include <iterator> #include <algorithm> #include <string> #include <set> #include <map> using namespace std; //cout<< //cin>> set<long long int>::iterator it; set<long long int>::iterator it1; bool pd(set<long long int > set1,set<long long int> set2) { if(set1.size()!=set2.size())return false; for(it=set1.begin(),it1=set2.begin();it!=set1.end();it++,it1++) { if(*it!=*it1)return false; } return true; } int main() { set<long long int> set1,set2; long long int x; while((cin>>x)) { if(x!=0)set1.insert(x); while(cin>>x&&x!=0) {set1.insert(x);} while(cin>>x&&x!=0) { set2.insert(x); } if(pd(set1,set2)==true)cout<<"YES"<<endl; else cout<<"NO"<<endl; set1.clear(); set2.clear(); } // // set_intersection()//交集 // set_union()//并集 // set_difference()//差集 // set_symmetric_difference() return 0; }这段代码哪里有问题

这段代码没有明显的语法错误，但是存在以下问题：

1. 函数 `pd()` 中的两个 `set` 传入的参数应该是 `const set<long long int>&` 类型，因为函数内部并不修改这两个参数。

2. 函数 `pd()` 中的两个 `set` 比较可以使用 `std::set::operator==` 来直接比较两个 `set` 是否相等，无需手动遍历比较。

3. 在输入数据时，当输入一个数为0时，程序会跳出第一个循环，但是没有清空输入流中的其他字符，导致第二个循环开始时读取到的是上一次输入流中的剩余字符，进而导致结果错误。

以下是修改后的代码：

#include <iostream>
#include <set>
using namespace std;

bool pd(const set<long long int>& set1, const set<long long int>& set2) {
    return set1 == set2;
}

int main() {
    set<long long int> set1, set2;
    long long int x;
    while (cin >> x) {
        if (x != 0) {
            set1.insert(x);
        }
        else {
            break;
        }
    }
    while (cin >> x) {
        if (x != 0) {
            set2.insert(x);
        }
        else {
            break;
        }
    }
    if (pd(set1, set2)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

#include <iostream> #include <vector> #include <unordered_map> #include <queue> #include <algorithm> using namespace std; struct WordFreq { string word; int freq; bool operator<(const WordFreq& other) const { return freq == other.freq ? word > other.word : freq < other.freq; } }; vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> freq; for (const auto& word : words) { freq[word]++; } priority_queue<WordFreq, vector<WordFreq>> pq; for (const auto& [word, f] : freq) { pq.push({word, f}); if (pq.size() > k) { pq.pop(); } } vector<string> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pq.top().word; pq.pop(); } return result; } int main() { int k; cin >> k; vector<string> words; string word; while (cin >> word) { if (word == "end") { break; } words.push_back(word); } auto result = topKFrequent(words, k); for (const auto& word : result) { cout << word << " "; } cout << endl; return 0; }

这段代码实现了前 k 个出现次数最多的单词的查找，使用了堆排序的思想，时间复杂度为 O(Nlogk)，其中 N 为单词个数。

具体实现过程如下：

1. 首先使用哈希表统计每个单词出现的频率。

2. 然后使用优先队列（堆）存储单词和对应的频率，队列中最多只保存 k 个元素。

3. 遍历哈希表中的每个元素，将其插入优先队列中，如果队列中元素数量超过 k，则将队列中频率最小的元素弹出。

4. 最后，将优先队列中的 k 个单词按频率从大到小排序，并返回结果。

以下是代码解释：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

// 定义一个结构体，用于存储单词和对应的频率
struct WordFreq {
  string word;
  int freq;
  bool operator<(const WordFreq& other) const {
      // 如果频率相同，按字母顺序从小到大排序；否则按频率从大到小排序
      return freq == other.freq ? word < other.word : freq > other.freq;
  }
};

vector<string> topKFrequent(vector<string>& words, int k) {
  // 哈希表用于统计每个单词出现的频率
  unordered_map<string, int> freq;
  for (const auto& word : words) {
      freq[word]++;
  }

  // 优先队列用于存储单词和对应的频率，队列中最多只保存 k 个元素
  priority_queue<WordFreq, vector<WordFreq>> pq;
  for (const auto& [word, f] : freq) {
      pq.push({word, f});
      if (pq.size() > k) {
          pq.pop();
      }
  }

  // 将优先队列中的 k 个单词按频率从大到小排序，并返回结果
  vector<string> result(k);
  for (int i = k - 1; i >= 0; i--) {
      result[i] = pq.top().word;
      pq.pop();
  }
  return result;
}

int main() {
  int k;
  cin >> k;

  vector<string> words;
  string word;
  while (cin >> word) {
      if (word == "end") {
          break;
      }
      words.push_back(word);
  }

  auto result = topKFrequent(words, k);
  for (const auto& word : result) {
      cout << word << " ";
  }
  cout << endl;

  return 0;
}

希望能够帮到你！