Làm thế nào để sort một mảng mà bộ nhộ chương trình cung cấp quá ít không đủ để đọc hết mảng.
Đây là ví dụ:
Cách giải quyết của mình.
Vì mình thấy 3mb chỉ lưu được khoảng hơn 770k phần tử float nên mình chọn 600k làm phần tử làm mốc để xử lý nhau sau:
Với trường hợp n (số phần tử của chương trình) < 600k… mình quicksort bình thường vì vẫn thõa mãn 3mb
Với trường họp n > 600k: thì mình đọc n/2 phần tử đầu và sort và ghi vào file1
mình đọc tiếp n - n/2 phần tử tiếp theo sort và ghi vào file2
(làm như vậy vì khi n > 3*1024*1024/4 thì mình không thể scanf được)
Cụ thể như ở đây:
#include <stdio.h>
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
typedef long long ll;
//[Codeforces Round #]
using namespace std;
float a[600000],b1, b2;
int n, m;
FILE *out1, *out2, *in1, *in2;
// phare 1
void process(){
int i, j;
out1 = fopen("1.tmp", "w");
out2 = fopen("2.tmp", "w");
// scanf("%d\n", &n);
m = n/2;
n -= m;
for(i=1; i<=n; i++) scanf("%f", &a[i]);
sort(a+1, a+n+1);
for(i=1; i<=n; i++) fprintf(out1, "%.2f ", a[i]);
for(i=1; i<=m; i++) scanf("%f", &a[i]);
sort(a+1, a+m+1);
for(i=1; i<=m; i++) fprintf(out2, "%.2f ", a[i]);
fclose(out1);
fclose(out2);
in1 = fopen("1.tmp", "r");
in2 = fopen("2.tmp", "r");
i = 1; j = 1;
fscanf(in1, "%f", &b1);
fscanf(in2, "%f", &b2);
while(i <= n && j <= m){
if (b1 < b2){
i++;
printf("%.2f ", b1);
if (i<=n)
fscanf(in1, "%f", &b1);
}
else{
j++;
printf("%.2f ", b2);
if (j<=m)
fscanf(in2, "%f", &b2);
}
}
while(i++ <= n){
printf("%.2f ", b1);
fscanf(in1, "%f", &b1);
}
while(j++ <= m){
printf("%.2f ", b2);
fscanf(in2, "%f", &b2);
}
}
// phare 2
void swap_(float *a, float *b) {
float tmp = *a;
*a = *b;
*b = tmp;
}
int partition_(int left, int right) {
float pivot = a[right];
int i = left - 1;
for(int j = left; j <= right - 1; j ++) {
if(a[j] > pivot) {
i++;
swap_(&a[j],&a[i]);
}
}
swap_(&a[i+1],&a[right]);
return (i+1);
}
void quickSort(int left, int right)
{
if (left < right)
{
int pivot_index = partition_(left, right);
quickSort(left, pivot_index - 1);
quickSort(pivot_index + 1, right);
}
}
void input( int n) {
for(int i = 0; i < n ; i ++) {
scanf("%f", &a[i]);
}
}
void output(int n) {
for(int i = n - 1; i >= 0 ; i--) {
printf("%.2f ", a[i]);
}
}
int main(){
scanf("%d",&n);
if( n > 600000) {
process();
} else {
input(n);
quickSort(0,n-1);
output(n);
}
return 0;
}
Nhưng vấn đề của mình gặp phải tiếp theo là TLE.
Mọi người xem và giúp mình tìm cách khắc phục với.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?