Форум программистов CodeGuru
16 Июль 2018, 04:55:03 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости:
 
   Начало   Помощь Войти Регистрация  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Построение  (Прочитано 15285 раз)
0 Пользователей и 1 Гость смотрят эту тему.
MahovIV
Новичок
*
Офлайн Офлайн

Сообщений: 3


Просмотр профиля
« : 01 Январь 2014, 17:07:27 »

Помогите решить задачу.
 Имя входного файла: 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;
}
Покажите правильно работающий вариант.
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!