vector常熟大,换成正常数组
by yinqf @ 2024-02-27 19:12:09
@[molsonsama](/user/1094817) ~~直接用 $sort$ 不香吗?~~(咳咳,快排请不要用 $vector$)
by __Rickysun__ @ 2024-02-27 19:16:41
@[yinqf](/user/673730) 之前换过了,但还是TLE
by molsonsama @ 2024-02-27 22:21:57
@[Rickysun](/user/824205) 这次是想手写一遍,所以没有用sort
by molsonsama @ 2024-02-27 22:22:34
@[yinqf](/user/673730) 这是我换过之后的代码,依然是前四个点AC,第五个点TLE。
```cpp
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
int vec[100001];
int partition(int left, int right) {
int num = rand() % (right - left + 1) + left;
swap(vec[num], vec[left]);
int part = vec[left];
int i = left, j = right;
while(i < j) {
while(vec[j] >= part && i < j)
j--;
while(vec[i] <= part && i < j)
i++;
if(i < j) swap(vec[i], vec[j]);
}
swap(vec[left], vec[i]);
return i;
}
void QuickSort(int left, int right) {
if(left >= right) return;
int mid = partition(left, right);
QuickSort(left, mid - 1);
QuickSort(mid + 1, right);
}
int main() {
srand(time(nullptr));
long long n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> vec[i];
}
QuickSort(0, n - 1);
for(int i = 0; i < n; i++) {
cout << vec[i] << " ";
}
return 0;
}
```
by molsonsama @ 2024-02-27 22:36:28
第五个的测试点是整个数组的数字全相同 你再调调看(我直接判相等就全输出 然后就过了...
by iamzhezhe520 @ 2024-03-14 20:31:28