Помогите решить задачу.
Имя входного файла: merge.dat
Имя выходного файла: merge.sol
Ограничение времени: 1 с
Ограничение памяти: 64 M
DOC-file
Капрал Арум столкнулся с неразрешимой для него задачей. Перед ним стоят две шеренги деревянных солдат Урфина Джюса (дуболомов), в каждой из них дуболомы расположены по росту (от самого высокого к самому низкому). Капралу необходимо построить дуболомов в одну шеренгу но так, чтобы они опять были расположены по росту от самого высокого к самому низкому.
Помогите капралу Аруму решить эту задачу.
Формат входного файла merge.dat
Текстовый файл merge.dat содержит четыре строки. В первой строке записано натуральное число N (1 ≤ N ≤ 100 000) — количество дуболомов в первой шеренге.
Вторая строка содержит N натуральных чисел, записанных через пробел. Числа идут в невозрастающем порядке. Каждое число лежит в диапазоне от 1 до 1 000 000 000.
В третьей строке записано натуральное число M (1 ≤ M ≤ 100 000) — количество дуболомов во второй шеренге.
Четвертая строка содержит M натуральных чисел, записанных через пробел. Числа идут в невозрастающем порядке. Каждое число лежит в диапазоне от 1 до 1 000 000 000.
Формат выходного файла merge.sol
Текстовый файл merge.sol должен содержать N+M чисел, идущих в невозрастающем порядке. Каждое число — это рост соответствующего дуболома из первой или из второй шеренги. Каждое число должно выводиться в отдельную строку.
Программа выглядит так.
#include <stdio.h>
int a[100000];
int mn = 0;
void merge(int l, int r) {
if (r == l)
return;
if (r - l == 1) {
if (a[r] < a[l]) {
mn = a[r];
a[r] = a[l];
a[l] = mn;
}
return;
}
int m = (r + l) / 2;
merge(l, m);
merge(m + 1, r);
int buf[100000];
int xl = l;
int xr = m + 1;
int cur = 0;
while (r - l + 1 != cur) {
if (xl > m)
buf[cur++] = a[xr++];
else if (xr > r)
buf[cur++] = a[xl++];
else if (a[xl] > a[xr])
buf[cur++] = a[xr++];
else buf[cur++] = a[xl++];
}
for (int i = 0; i < cur; i++)
a[i + l] = buf[i];
}
int main() {
int F, L, b[100000], c[100000], k = 0, i = 0, f = 0, j, min = 0, mn = 0;
FILE *fp, *mp;
fp = fopen("merge.dat", "r");
fscanf(fp, "%d", &F);
for(k = 0; k < F; k++) {
fscanf(fp, "%d", &a[k]);
}
fscanf(fp, "%d", &L);
for(i = 0; i < L; i++) {
fscanf(fp, "%d", &b[i]);
}
fclose(fp);
while(F > 0) {
c[f] = a[k];
k++;
f++;
F--;
}
while(L > 0) {
c[f] = b[i];
i++;
f++;
L--;
}
merge(0, f - 1);
mp = fopen("merge.dat", "w");
for(i = 0; i < f; i++) {
fprintf(mp, "%d\n", c[i]);
}
fclose(mp);
return 0;
}
Покажите правильно работающий вариант.
