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

Жадный алгоритм С++

14.04.2015, 19:37. Показов 3960. Ответов 2
Метки нет (Все метки)

С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну операцию объединяются 2 счета и банк автоматически перечисляет на свой счет Р% от суммы объединения за выполнение операции и закрытие одного из счетов. Какая наибольшая сумма может остаться на счету фирмы? На каждом из счетов до внедрения политики объединения было не более чем G грн.

Входные данные

В первой строке 2 числа: количество счетов N и процент отчислений P.

Во второй строке N чисел: сумма на каждом из счетов фирмы.

Выходные данные

Наибольшая сумма, которая может остаться на счету.

2 ≤ N ≤ 100000
0 ≤ Р ≤ 20
0 ≤ G ≤ 10000

Пример входных данных
4 5
1000 1100 1200 1300

Пример выходных данных
4151.50

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
#include <iostream>
 
using namespace std;
 
 
int main()
{
 int n,i,j;
 double p,a[100000],temp;
 
 cin>>n>>p;
 for (int u=0;u<n;u++)
 {
     cin>>a[u];
 }
 
 for (int t=0;t<(n-1);t++)
     if (a[t]>a[t+1])
     {
         temp=a[t];
         a[t]=a[t+1];
         a[t+1]=temp;
     }
 
 while (true)
 {
     j=0;
     if (n==1)
         break;
 
     if (n%2==0)
     for (i=0;i<n;i+=2)
     {
         a[j]=(a[i]+a[i+1])*(1-p/100);
         j++;
     }
     else
     {
             for (i=0;i<n-1;i+=2)
         {
             a[j]=(a[i]+a[i+1])*(1-p/100);
             j++;
         }
             a[j]=a[i]*(1-p/100);
     }
 
     if (n%2==0)
         n/=2;
     else
         n=n/2+1;
 }
 
 printf("%.2f\n", a[0]);
 
 
 return 0;
}
Засчитано лишь 15% тестов. Кто может объяснить в чем проблема?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.04.2015, 19:37
Ответы с готовыми решениями:

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

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

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

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

2
490 / 386 / 184
Регистрация: 08.04.2013
Сообщений: 1,673
14.04.2015, 20:28 2
зависит как объединяешь, твой алгоритм я не разбирал. Может прокатить в данном случае 2 варианта.
1 объединение 2 рядом стоящих пар или 2х самых отдаленных, но не прокатит объединение 2 первых потом с 3 потом с 4.
пробуй по обоим вариантам. Причин не знаю, не математик и не банкир
Надо наверное объединять наиболее близкие по сумме счета

Добавлено через 9 минут
А может и объединение счетов которые в сумме дают наибольшее приближение к (среднему*2)
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
15.04.2015, 17:32 3
Ну, если учесть, что
Цитата Сообщение от CF asker Посмотреть сообщение
a[j]=(a[i]+a[i+1])*(1-p/100);
то удивительно, что вообще что-то
Цитата Сообщение от CF asker Посмотреть сообщение
Засчитано
Добавлено через 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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/////////////////////////////////////////////////////////////////////////////////////////
//С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. 
//За одну операцию объединяются 2 счета и банк автоматически перечисляет на свой счет Р% 
//от суммы объединения за выполнение операции и закрытие одного из счетов. Какая наибольшая 
//сумма может остаться на счету фирмы? На каждом из счетов до внедрения политики объединения 
//было не более чем G грн.
 
//ВХОДНЫЕ ДАННЫЕ
//В первой строке 2 числа: количество счетов N и процент отчислений P.
//Во второй строке N чисел: сумма на каждом из счетов фирмы.
//
//ВЫХОДНЫЕ ДАННЫЕ
//Наибольшая сумма, которая может остаться на счету.
//
//2 ≤ N ≤ 100000
//0 ≤ Р ≤ 20
//0 ≤ G ≤ 10000
//
//ПРИМЕР ВХОДНЫХ ДАННЫХ
//4 5
//1000 1100 1200 1300
//
//ПРИМЕР ВЫХОДНЫХ ДАННЫХ
//4151.50
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <set>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                      T_account;
typedef double                      T_percentage;
typedef std::multiset<T_account>    T_accounts;
/////////////////////////////////////////////////////////////////////////////////////////
T_account   merge_pair_of_accounts_with_percentage_and_get
    (
        T_account       A,
        T_account       B,
        T_percentage    P
    )
{
    return      (
                    A + B
                )
                *   ( 100 - P )
                /   100;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_account   erase_front_and_get( T_accounts  &   accounts )
{
    T_account   front_account    =   *accounts.begin();
    accounts.erase( front_account );
    return  front_account;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_account   merge_accounts_into_one_with_percentage_and_get
    (
        T_accounts      accounts,
        T_percentage    P
    )
{
    while( accounts.size() > 1 )
    {
        accounts.insert
            (
                merge_pair_of_accounts_with_percentage_and_get
                    (
                        erase_front_and_get( accounts ),
                        erase_front_and_get( accounts ),
                        P
                    )
            );
    }
 
    return  erase_front_and_get( accounts );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    std::cout   <<  "Введите количество счетов N, процент отчислений P,\nдалее строку из N сумм счетов:"
                <<  std::endl;
 
    int     N  =   0;
    std::cin    >>  N;
    T_percentage    P   =   0;
    std::cin    >>  P;
 
    T_accounts  accounts;
 
    for( int  i = 0; i < N; ++i )
    {
        T_account   cur_account;
        std::cin    >>  cur_account;
        accounts.insert( cur_account );
    }
 
    std::cout   <<  merge_accounts_into_one_with_percentage_and_get
                        (
                            accounts,
                            P
                        )
 
                <<  std::endl;
 
    system("pause");
}
Добавлено через 4 часа 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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/////////////////////////////////////////////////////////////////////////////////////////
//С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. 
//За одну операцию объединяются 2 счета и банк автоматически перечисляет на свой счет Р% 
//от суммы объединения за выполнение операции и закрытие одного из счетов. Какая наибольшая 
//сумма может остаться на счету фирмы? На каждом из счетов до внедрения политики объединения 
//было не более чем G грн.
 
//ВХОДНЫЕ ДАННЫЕ
//В первой строке 2 числа: количество счетов N и процент отчислений P.
//Во второй строке N чисел: сумма на каждом из счетов фирмы.
//
//ВЫХОДНЫЕ ДАННЫЕ
//Наибольшая сумма, которая может остаться на счету.
//
//2 ≤ N ≤ 100000
//0 ≤ Р ≤ 20
//0 ≤ G ≤ 10000
//
//ПРИМЕР ВХОДНЫХ ДАННЫХ
//4 5
//1000 1100 1200 1300
//
//ПРИМЕР ВЫХОДНЫХ ДАННЫХ
//4151.50
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <set>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                      T_account;
typedef double                      T_percentage;
typedef std::multiset<T_account>    T_accounts;
/////////////////////////////////////////////////////////////////////////////////////////
T_account   merge_pair_of_accounts_with_percentage_and_get
    (
        T_account       A,
        T_account       B,
        T_percentage    P
    )
{
    return      (
                    A + B
                )
                *   ( 100 - P )
                /   100;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_account   erase_front_and_get( T_accounts  &   accounts )
{
    T_account   front_account    =   *accounts.begin();
 
    accounts.erase
        (
            accounts.begin()
        );
 
    return  front_account;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_account   merge_accounts_into_one_with_percentage_and_get
    (
        T_accounts      accounts,
        T_percentage    P
    )
{
    while( accounts.size() > 1 )
    {
        accounts.insert
            (
                merge_pair_of_accounts_with_percentage_and_get
                    (
                        erase_front_and_get( accounts ),
                        erase_front_and_get( accounts ),
                        P
                    )
            );
    }
 
    return  erase_front_and_get( accounts );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    std::cout   <<  "Введите количество счетов N, процент отчислений P,\nдалее строку из N сумм счетов:"
                <<  std::endl;
 
    int     N  =   0;
    std::cin    >>  N;
    T_percentage    P   =   0;
    std::cin    >>  P;
 
    T_accounts  accounts;
 
    for( int  i = 0; i < N; ++i )
    {
        T_account   cur_account;
        std::cin    >>  cur_account;
        accounts.insert( cur_account );
    }
 
    std::cout   <<  merge_accounts_into_one_with_percentage_and_get
                        (
                            accounts,
                            P
                        )
 
                <<  std::endl;
 
    system("pause");
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.04.2015, 17:32
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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