Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
skeivoker
0 / 0 / 0
Регистрация: 27.05.2015
Сообщений: 10
#1

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

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

Вот мое задание:

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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2015, 19:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Жадный алгоритм нахождения абсолютной разницы чисел (C++):

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

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

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

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

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

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

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

Добавлено через 3 минуты
и ещё:
зачем код красным выделять?
Глаза немного режет
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 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
zer0mail
2334 / 1960 / 192
Регистрация: 03.07.2012
Сообщений: 7,030
Записей в блоге: 1
02.09.2015, 11:08 #4
Это ж надо столько извратов для вывода абсолютной разницы двух чисел
0
Kuziaka
6 / 6 / 2
Регистрация: 22.07.2015
Сообщений: 36
02.09.2015, 15:49 #5
Цитата Сообщение от zer0mail Посмотреть сообщение
Это ж надо столько извратов для вывода абсолютной разницы двух чисел
+1
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2015, 15:49
Привет! Вот еще темы с ответами:

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

Жадный граф/алгоритм - C++
Требуется написать программу с графическим интерфейсом: пользователь задаёт точки (A, B, C и т.д.). Далее соединяет между собой какие-то...

Жадный алгоритм (рюкзак) - C++
слишком медленно, но верно работает программа. Помогите пожалуйста ускорить. (извиняюсь за транслит или что-то похожее на него) ...

Жадный алгоритм на графе - C++
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть, дан ориентированный взвешенный граф (можно...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.09.2015, 15:49
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru