#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; }的时间复杂度
时间: 2024-04-06 11:32:26 浏览: 19
这段代码的时间复杂度为 $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){ short kState = GetAsyncKeyState('K'); if(kState&0x8000){ while(1){ Sleep(550); simulateScrollUp(); if(kState&0x8000){ break; } } } } return 0; } 我这个代码是按下k重复执行过0.55秒快速点一下蹲,在这里循环里在按一下蹲退出这个循环,代码有问题,你看看错哪了,然后帮我改改
你的代码有一个问题在于内层循环中没有更新`kState`的值,导致无法正确判断是否按下或抬起K键。此外,你的代码中也没有退出内层循环的逻辑。以下是修改后的代码:
```cpp
#include <iostream>
#include <windows.h>
#include <ctime>
#include <conio.h>
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));
bool isPressed = false; // 标记K键是否被按下
while (true) {
if (GetAsyncKeyState('K') & 0x8000) {
if (!isPressed) { // K键刚被按下
isPressed = true;
simulateScrollUp();
}
}
else {
if (isPressed) { // K键刚被抬起
isPressed = false;
break; // 退出循环
}
}
Sleep(100); // 等待一段时间,减少CPU占用
}
return 0;
}
```
在修改后的代码中,我们添加了一个布尔型变量`isPressed`,用于标记K键的按下状态。当检测到K键按下时,如果`isPressed`为`false`,表示K键刚被按下,则执行`simulateScrollUp()`函数来模拟滚动。当K键抬起时,如果`isPressed`为`true`,表示K键刚被抬起,则退出循环。
同时,我们还在循环中添加了一个延时(`Sleep(100)`)来减少CPU占用。这样可以让循环每次迭代之间有一定的间隔,避免不必要的资源浪费。
请注意,由于你的代码主要涉及输入和窗口操作,因此可能只在Windows平台上有效。
#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))。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)