#include<bits/stdc++.h> using namespace std; int n,m; int main() { srand(time(0)); cin>>n>>m; vector<int> time(n); vector<vector<int> > machine(m); vector<int> sumTime(m,0); for(int i=0;i<n;++i){ time[i]=rand()%30+1; cout<<time[i]<<setw(3); } sort(time.begin(),time.end(),greater<int>()); for(int i=0;i<n;++i){ int select=0; for(int j=0;j<m;++j){ if(sumTime[j]<sumTime[select]){ select=j; } } machine[select].push_back(time[i]); sumTime[select]+=time[i]; } int maxTime=sumTime[0]; for(int j=0;j<m;++j){ if(sumTime[j]>maxTime){ maxTime=sumTime[j]; } } for(int j=0;j<m;++j){ cout<<"第"<<j+1<<"台机器所需处理总时间为: "<<sumTime[j]<<endl; } cout<<"处理所有作业时间共需: "<<maxTime; return 0; }的时间复杂度

这段代码的时间复杂度为 $O(nm\log m)$，其中 $n$ 是作业的数量，$m$ 是机器的数量。

首先，生成随机数的时间复杂度为 $O(n)$，因为需要生成 $n$ 个随机数。然后，对随机数进行排序的时间复杂度为 $O(n\log n)$，因为使用的是 `sort` 函数，它的时间复杂度是 $O(n\log n)$。接着，对于每一个作业，需要在所有可用机器中选择一个空闲时间最短的机器进行调度，这个过程的时间复杂度为 $O(nm)$。在选择机器的过程中，需要遍历所有机器，因此时间复杂度为 $O(m)$。因此，总的时间复杂度为 $O(nm\log n)$。

需要注意的是，在实际情况中，机器数量 $m$ 通常比作业数量 $n$ 小得多，因此可以将时间复杂度近似看作 $O(n\log n)$。

相关问题

#include <bits/stdc++.h> #include <windows.h> #include <ctime> #include <conio.h> using namespace std; void simulateScrollUp() { INPUT input; input.type = INPUT_MOUSE; input.mi.dx = 0; input.mi.dy = 0; input.mi.mouseData = 120; // 设置滚动量 input.mi.dwFlags = MOUSEEVENTF_WHEEL; input.mi.time = 0; input.mi.dwExtraInfo = 0; SendInput(1, &input, sizeof(INPUT)); } int main(){ SetConsoleTitle(""); SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN); srand((unsigned)time(NULL)); int cnt=0; while(1){ if(GetAsyncKeyState('K') & 0x8000){ cnt++; while(cnt%2!=0){ Sleep(250); simulateScrollUp(); if (GetAsyncKeyState('K') & 0x8000){ cnt++; } } } } return 0; } 这代码为什么在重复循环的重复循环里按k跳不出那个重复循环

根据你提供的代码，重复循环是由 `while(1)` 条件实现的。在这个循环内部，你使用了 `GetAsyncKeyState('K')` 来检测是否按下了 'K' 键。然后，当 `cnt` 是奇数时，你调用了 `simulateScrollUp()` 函数，并在 `GetAsyncKeyState('K')` 返回 true 时增加了 `cnt` 的值。

然而，在循环内部，你没有对 `cnt` 的值进行更新，因此它将一直保持为奇数。这导致了 `simulateScrollUp()` 函数的连续调用，而不会再次检查 `GetAsyncKeyState('K')` 的状态。因此，按下 'K' 键时无法跳出循环。

为了解决这个问题，你可以在按下 'K' 键时将 `cnt` 增加2而不是1，这样在下一次循环中 `cnt` 将变为偶数，并且可以跳出重复循环。请尝试将以下行代码修改为：

if (GetAsyncKeyState('K') & 0x8000){
    cnt += 2; // 将 cnt 增加2
}

这样应该可以解决你的问题。

#include <bits/stdc++.h> using namespace std; string s1,s2; int cnt1,cnt2; string cann(const string &s){ cnt1++; int n=s.size(); if(n%2){ return s; } string a=s.substr(0,n/2); string b=s.substr(n/2,n/2); a=cann(a); b=cann(b); if(b<a){ swap(a,b); } return a+b; } bool g(int l1,int r1,int l2,int r2){ cnt2++; string a=s1.substr(l1,r1-l1+1),b=s2.substr(l2,r2-l2+1); if(a==b){ return 1; }else if((r1-l1+1)%2 || (r2-l2+1)%2){ return 0; } int mid1=(l1+r1)/2,mid2=(l2+r2)/2; if(g(l1,mid1,l2,mid2)&&g(mid1+1,r1,mid2+1,r2)||g(l1,mid1,mid2+1,r2)&&g(mid1+1,r1,l2,mid2)){ return 1; } return 0; } int main(){ for(int i=1;i<=1000000;i++){ for(int j=1;j<=3;j++){ s1=s2=""; srand(time(NULL)); for(int k=1;k<=pow(2,j);k++){ s1+=char(rand()%26+'a'); } for(int k=1;k<=pow(2,j);k++){ s2+=char(rand()%26+'a'); } cnt1=cnt2=0; if(cann(s1)==cann(s2)){ cout << "YES" <<endl; }else{ cout << "NO" << endl; } if(g(0,s1.size()-1,0,s2.size()-1)){ cout << "YES" << endl; }else{ cout << "NO" << endl; } cout << s1 << " " << s2 << endl; cout << setw(5) << cnt1; cout << setw(5) << cnt2; cout << " " << (cnt1<=cnt2) << endl; } } return 0; } 那个函数时间复杂度更低

对于给定的代码，我们可以看到两个函数：cann和g。让我们分别来分析它们的时间复杂度：

1. 函数cann：
- 首先，它递归地将输入的字符串分成两半，并对每一半进行递归调用。
- 然后，它将两个字符串拼接在一起，并返回结果。
- 由于每次调用都将字符串长度减半，所以递归的深度最多为log(n)，其中n是输入字符串的长度。
- 每一次递归调用中，需要将两个子字符串进行拼接，这需要O(n)的时间复杂度（n是子字符串的长度）。
- 因此，总的时间复杂度为O(nlog(n))。

2. 函数g：
- 它通过递归地比较两个子字符串是否相等来判断整个字符串是否相等。
- 每次递归调用中，需要将子字符串分成两半，并对每一半进行递归调用。
- 由于每次调用都将字符串长度减半，所以递归的深度最多为log(n)，其中n是输入字符串的长度。
- 每一次递归调用中，需要比较两个子字符串是否相等，这需要O(n)的时间复杂度（n是子字符串的长度）。
- 因此，总的时间复杂度为O(nlog(n))。

综上所述，两个函数的时间复杂度是一样的，都是O(nlog(n))。