Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/18: Рейтинг темы: голосов - 18, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 27.05.2015
Сообщений: 10

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

01.09.2015, 19:36. Показов 3446. Ответов 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
01.09.2015, 19:36
Ответы с готовыми решениями:

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

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

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

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

Добавлено через 3 минуты
и ещё:
зачем код красным выделять?
Глаза немного режет
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
02.09.2015, 01:44
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
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
02.09.2015, 11:08
Это ж надо столько извратов для вывода абсолютной разницы двух чисел
0
 Аватар для Kuziaka
6 / 6 / 3
Регистрация: 22.07.2015
Сообщений: 36
02.09.2015, 15:49
Цитата Сообщение от zer0mail Посмотреть сообщение
Это ж надо столько извратов для вывода абсолютной разницы двух чисел
+1
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
02.09.2015, 15:49
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru