0 / 0 / 0
Регистрация: 27.05.2015
Сообщений: 10
1

Жадный алгоритм нахождения абсолютной разницы чисел

01.09.2015, 19:36. Показов 3141. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вот мое задание:

A. Дело о нулях и единицах
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андроид Андреид — известный на всю галактику детектив. В свободное от работы время он размышляет о строках из нулей и единиц.

Как-то раз ему в голову пришла строка длины n, состоящая из нулей и единиц. Рассмотрим следующую операцию — мы выбираем любые две соседние позиции в строке, и если в одной из них ноль, а в другой — единица, то разрешается удалить обе эти цифры, в результате чего строка строка становится длины n - 2.

Андреид задумался — какой минимальной длины строка может остаться, если примененить описанную операции некоторое (возможно, нулевое) количество раз?
Входные данные

В первой строке входных данных задано целое число n (1 ≤ n ≤ 2·105) — длина строки, которая пришла в голову Андреиду.

Во второй строке записана строка длины n, состоящая из нулей и единиц.
Выходные данные

Выведите единственное целое число — минимальное возможное значение длины строки, которая останется после применения операций, описанных в условии задачи.
А вот мой код:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdlib>
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
int x = 0;
 
zadanie(int* mass1, int n, int one, int two)
{
    if(two<n)
    {
        if(mass1[one]!=mass1[two])
        {
            for(int i=one; i<n; i++)
            {
                mass1[i] = mass1[i+2];
            }
            n = n-2;
            if(n==1)
            {
                return x=1;
            }
            if(n==0)
            {
                return x=0;
            }
            if(one>0)
            {
                zadanie(mass1, n, one-1, two-1);
            }
            else
            {
                zadanie(mass1, n, one, two);
            }
        }
        else
        {
            if(n>2)
            {
                x++;
                zadanie(mass1, n, one+1, two+1);
            }
            else
            {
                return x=2;
            }
        }
    }
    return 0;
}
 
int main() 
{
    int n;
    cin>> n;
    char s[n];
    cin>> s;
    int* mass1 = new int[n];
    for(int i=0; i<n; i++)
        mass1[i]=s[i]-'0';
    if(n>1)
    {
        zadanie(mass1, n, 0, 1);
        cout<< x;
    }
    else
    {
        cout<< 1;
    }
    delete []mass1;
    return 0;
}

Неправильный ответ в 11 тесте. Помогите исправить программу и сделать ее полностью рабочей.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.09.2015, 19:36
Ответы с готовыми решениями:

Написать функцию нахождения в массиве целых чисел наименьшего по абсолютной величине числа.
Написать функцию нахождения в массиве целых чисел наименьшего по абсолютной величине числа.

Написать функцию нахождения в массиве целых чисел наименьшего по абсолютной величине числа.
Написать функцию нахождения в массиве целых чисел наименьшего по абсолютной величине числа.

Жадный алгоритм
Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно...

Жадный алгоритм
Добрый день. Помогите, пожалуйста, понять, где затаилась ошибка. Это задачка на жадный алгоритм:...

4
6 / 6 / 3
Регистрация: 22.07.2015
Сообщений: 36
01.09.2015, 20:32 2
Вам обязательно ЭТУ программу исправить или натолкнуть на решение(которое между прочим можно посмотреть на codeforces у других людей и это абсолютно нормально),
просто там всё куда проще
Ваш код не совсем понятен

Добавлено через 3 минуты
и ещё:
зачем код красным выделять?
Глаза немного режет
0
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
02.09.2015, 01:44 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
typedef long long       T_int;
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int     n   =   0;
    std::cin    >>  n;
 
    T_str   s;
    std::cin    >>  s;
 
    std::cout   <<  abs (
                                n
                            -       std::count
                                        (
                                            s.begin     (),
                                            s.end       (),
                                            '1'
                                        )
                                *   2
                        )
 
                <<  std::endl;
 
    //system("pause");
}
0
2663 / 2238 / 240
Регистрация: 03.07.2012
Сообщений: 8,141
Записей в блоге: 1
02.09.2015, 11:08 4
Это ж надо столько извратов для вывода абсолютной разницы двух чисел
0
6 / 6 / 3
Регистрация: 22.07.2015
Сообщений: 36
02.09.2015, 15:49 5
Цитата Сообщение от zer0mail Посмотреть сообщение
Это ж надо столько извратов для вывода абсолютной разницы двух чисел
+1
0
02.09.2015, 15:49
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.09.2015, 15:49
Помогаю со студенческими работами здесь

Жадный алгоритм С++
С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну...

жадный алгоритм
написать программу для жадного алгоритма, если не сложно с комментариями в действиях

Жадный алгоритм
Задача: По следам олимпиады. Известно, что оптимальным выбором лыж является такой, когда длина лыж...

Жадный алгоритм
Суть задачи - имеется N предметов различного размера. Один ящик имеет строгую вместимость....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru