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

Листы жести - минимальную площадь - C++

Восстановить пароль Регистрация
 
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
27.04.2012, 15:14     Листы жести - минимальную площадь #1
Задача

На складе хранятся прямоугольные листы жести разных размеров. Листы расположены горизонтально на полу. Для экономии поверхности, они накладываются друг на друга, но так, чтобы лист лежащий выше, в целом размере был размещен на листе, который находится под ним. Кладовщик заботится о том, чтобы соответствующие края листов жести были параллельными, а в середины листов создавали единую стопку, лежа на одной вертикали. Чтобы приспособиться к листу жести, который находится ниже можно поворачивать его на 90 градусов вокруг центра.

Задание:

Напишите программу, которая для данных листов жести обсчитает минимальную площадь пола, учитывая вышеназванные требования.

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

Стандартный вход содержит несколько наборов данных. Первая строка содержит один набор, неотъемлемое целое n (n <= 200) которое указывает на количество листов в проблеме. Если он равен 0, это означает конец данных. В последующих строках n содержит два положительных целых числа, означающие размеры листов в наборе данных.

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

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

Пример

Для входных данных:
2
3 5
4 4
3
5 4
2 5
4 4
0

Правильный ответ:
31
30

Вот мой код программы:
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
#include <iostream>
#include <fstream>
#define N 200
 
using namespace std; 
int main()
{
    ifstream in("input.txt");
    if (!in)
    {
        cerr<< "There's no such file";
        return 1;
    }
    ofstream out("output.txt");
    
    int w_tab[N];    
    int h_tab[N];
    int s_tab[N];
    int id, w, h;
    while (!in.eof())
    {
        in>> id;
        if (id == 0) break;
        for (int i = 0; i < id; i++)
        {
            in>> w>> h;
            w_tab[i]=w;
            h_tab[i]=h;
            
            
            for (int j = 1; j < id; j++)
            {
                if(w_tab[j]<=w_tab[j+1] && h_tab[j]<=h_tab[j+1]){
                
                w_tab[j]=w_tab[j+1];
                w_tab[j+1]=0;
                
                h_tab[j]=h_tab[j+1];
                h_tab[j+1]=0;          
                }
                
                else if(w_tab[j]<=h_tab[j+1] && h_tab[j]<=w_tab[j+1]){
 
                w_tab[j]=w_tab[j+1];
                w_tab[j+1]=0;
                
                h_tab[j]=h_tab[j+1];
                h_tab[j+1]=0;          
                }
                     
            } 
            //out<< w_tab[i]<< h_tab[i]<<"\n"; 
            s_tab[i] += w_tab[i] * h_tab[i];
            out<< s_tab[i]<< "\n";  
            }
    }
    out.close();
    return 0;
}
Помогите решить эту задачку!

Проблема в с работой над массивами не могу понять в чем моя проблема и в файл output.txt тоже сохраняет мусор.

Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2012, 15:14     Листы жести - минимальную площадь
Посмотрите здесь:

Вывести минимальную прибыль C++
Составить базу данных о квартирах дома (от 6 до 12). Для каждой квартиры указать номер, жилую площадь, общую площадь, количество жильцов... C++
Найти минимальную суммарную длину n отрезков C++
C++ По заданному числу n вычислить минимальную сумму чисел
Найти максимальную, минимальную и среднюю температуру воздуха C++
Найти минимальную длину пути C++
C++ Определить площадь круга и площадь заштрихованных областей
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
JokerNN
132 / 128 / 36
Регистрация: 29.12.2011
Сообщений: 359
27.04.2012, 17:20     Листы жести - минимальную площадь #2
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
#include <iostream>
#include <fstream>
//real steel
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void special_bubblesort(int arr[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size - i; ++j) {
            if(arr[j][0] > arr[j-1][0] || (arr[j][0] == arr[j-1][0] && arr[j][1] > arr[j-1][1])) {
                swap(&arr[j][0], &arr[j-1][0]);
                swap(&arr[j][1], &arr[j-1][1]);
            }
        }
    }
}
 
int area(int arr[][2], int size)
{
    int area=arr[0][0]*arr[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((arr[i][0] > arr[i-1][0] && arr[i][0] > arr[i-1][1]) || (arr[i][1]>arr[i-1][0] && arr[i][1] > arr[i-1][1])) area+=arr[i][0]*arr[i][1];
    }
    return area;
}
 
int main()
{
    int n;
    ifstream in("input.txt");
    ofstream out("output.txt");
    in>>n;
    while (n)
    {
        int parameters[n][2];
        for (int i=0; i<n; ++i) in>>parameters[i][0]>>parameters[i][1];
        special_bubblesort(parameters, n);
        out<<area(parameters, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
    return 0;
}
Вроде бы так, но на 100% алгоритм не тестировал, ещё не сделал проверки на открытие\закрытие файла, верность данных, программа предполагает, что всё введено корректно и файлы открылись.

По алгоритму: сортируем массив с размерами листов по неубыванию, в качестве старшего разряда выступает 1й параметр, младшего - 2й. Т.е. 2й данный вами пример будет отсортирован как (5,4) (4,4) (2,5) (по аналогии 54, 44, 25). Затем эти листы складываются друг на друга, если следующий лист не может быть положен на предыдущий - он кладётся рядом. В точности алгоритма, повторюсь на 100% не уверен (возможно стоит сначала их повернуть таким образом, чтобы длина обязательно была больше/равна ширине). На ваших данных сработало всё как надо. Если что, вечером, придя домой, доделаю.
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
27.04.2012, 21:01  [ТС]     Листы жести - минимальную площадь #3
Для этих входных данных

2
3 5
4 4
3
5 4
2 5
4 4
4
4 4
5 3
4 4
5 3
3
5 5
4 4
6 5
5
5 5
4 4
5 6
5 5
6 5
0
ответ должен быть

31
30
31
30
30

а программа выдает

31
30
15
30
30

то есть для

4
4 4
5 3
4 4
5 3

должно быть 31 а есть 15

для
7
3 2
2 3
4 4
4 2
2 4
4 4
5 5

должно быть 25 а есть 33
спасибо за помощь вы мне очень помогли!
JokerNN
132 / 128 / 36
Регистрация: 29.12.2011
Сообщений: 359
28.04.2012, 14:29     Листы жести - минимальную площадь #4
Цитата Сообщение от shchurkoroman Посмотреть сообщение
спасибо за помощь вы мне очень помогли!
sarcasm?)
А вообще позор мне за хитросделанную сортировку) Переделал, теперь сортирует по убыванию площади листа, эта версия прошла все вышеобозначенные тесты) Сразу извиняйте меня, сам я тестировать свой код не привык)
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
#include <iostream>
#include <fstream>
//real steel 2
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void special_bubblesort(int arr[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(arr[j][0]*arr[j][1] > arr[j-1][0]*arr[j-1][1]) {
                swap(&arr[j][0], &arr[j-1][0]);
                swap(&arr[j][1], &arr[j-1][1]);
            }
        }
    }
}
 
int area(int arr[][2], int size)
{
    int area=arr[0][0]*arr[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((arr[i][0] > arr[i-1][0] && arr[i][0] > arr[i-1][1]) || (arr[i][1] > arr[i-1][0] && arr[i][1] > arr[i-1][1])) area += arr[i][0]*arr[i][1];
    }
    return area;
}
 
int main()
{
    int n;
    ifstream in("input.txt");
    ofstream out("output.txt");
    in>>n;
    while (n)
    {
        int parameters[n][2];
        for (int i=0; i<n; ++i) in>>parameters[i][0]>>parameters[i][1];
        special_bubblesort(parameters, n);
        out<<area(parameters, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
    return 0;
}
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
28.04.2012, 14:59  [ТС]     Листы жести - минимальную площадь #5
Спасибо большое!
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
05.06.2012, 19:14  [ТС]     Листы жести - минимальную площадь #6
Всем привет доработал программу но НЕ ДО КОНЦА
вот код:

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
#include <iostream>
#include <fstream>
 
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void bubblesort(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=0; j < size-i; ++j) {
            if(tab[j][1]<tab[j][0]){
                swap(&tab[j][0], &tab[j][1]);
            }
        }
    }
}
 
void bubblesort1(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]>tab[j-1][0]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
void bubblesort2(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]*tab[j][1] > tab[j-1][0]*tab[j-1][1]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
int square(int tab[][2], int size)
{
    int square=tab[0][0]*tab[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((tab[i][0] > tab[i-1][0] && tab[i][0] > tab[i-1][1]) || (tab[i][1] > tab[i-1][0] && tab[i][1] > tab[i-1][1])) square += tab[i][0]*tab[i][1];
    }
    return square;
}
 
int main()
{
    int n,k;
    
    cin>>k;
    while (k)
    {
        int rozmiar[k][2];
        for (int i=0; i<k; ++i) cin>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, k);
        bubblesort1(rozmiar, k);
        bubblesort2(rozmiar, k);
        cout<<square(rozmiar, k)<<endl;
        cin>>k;
    }
 
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    in>>n;
    while (n)
    {
        int rozmiar[n][2];
        for (int i=0; i<n; ++i) in>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, n);
        bubblesort1(rozmiar, n);
        bubblesort2(rozmiar, n);
        out<<square(rozmiar, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
 
    return 0;
}

для данных

14
20 1
1 19
2 9
2 10
1 15
4 5
9 2
1 8
2 7
2 9
7 2
2 3
4 4
4 3

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
2 4

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
9 4
0

результат должен быть

150
143
196

А у меня
83
143
136
Помогите решыть даную проблему!

Добавлено через 48 минут
Цитата Сообщение от shchurkoroman Посмотреть сообщение
Всем привет доработал программу но НЕ ДО КОНЦА
вот код:

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
#include <iostream>
#include <fstream>
 
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void bubblesort(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=0; j < size-i; ++j) {
            if(tab[j][1]<tab[j][0]){
                swap(&tab[j][0], &tab[j][1]);
            }
        }
    }
}
 
void bubblesort1(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]>tab[j-1][0]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
void bubblesort2(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]*tab[j][1] > tab[j-1][0]*tab[j-1][1]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
int square(int tab[][2], int size)
{
    int square=tab[0][0]*tab[0][1];
    for(int i=1; i < size; ++i)
    {
        if ((tab[i][0] > tab[i-1][0] && tab[i][0] > tab[i-1][1]) || (tab[i][1] > tab[i-1][0] && tab[i][1] > tab[i-1][1])) square += tab[i][0]*tab[i][1];
    }
    return square;
}
 
int main()
{
    int n,k;
    
    cin>>k;
    while (k)
    {
        int rozmiar[k][2];
        for (int i=0; i<k; ++i) cin>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, k);
        bubblesort1(rozmiar, k);
        bubblesort2(rozmiar, k);
        cout<<square(rozmiar, k)<<endl;
        cin>>k;
    }
 
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    in>>n;
    while (n)
    {
        int rozmiar[n][2];
        for (int i=0; i<n; ++i) in>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, n);
        bubblesort1(rozmiar, n);
        bubblesort2(rozmiar, n);
        out<<square(rozmiar, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
 
    return 0;
}

для данных

14
20 1
1 19
2 9
2 10
1 15
4 5
9 2
1 8
2 7
2 9
7 2
2 3
4 4
4 3

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
2 4

12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
9 4
0

результат должен быть

150
143
196

А у меня
83
143
136
Помогите решыть даную проблему!
Проблема в сортировке только где она? Помогите разобраться!
JokerNN
132 / 128 / 36
Регистрация: 29.12.2011
Сообщений: 359
05.06.2012, 20:47     Листы жести - минимальную площадь #7
Зачем целых 3 сортировки?) Думается мне сначала надо отсортировать по убыванию площади, затем просто каждый лист "повернуть" так чтобы длинная кромка была всегда слева, например, потом пытаться складывать и, если одна из сторон больше чем у листа ниже - то кладём рядом, могу на выходных доделать, сейчас, к сожалению, у самого сессия.

P.S. Nice Prepod
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
05.06.2012, 20:56  [ТС]     Листы жести - минимальную площадь #8
Для данных

3
1 20
4 5
10 2

программа не работает для этого там 3 сортировки!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.06.2012, 06:10     Листы жести - минимальную площадь #9
shchurkoroman, Пробуйте такой алгоритм:
При считывании очередного набора данных, например:
Цитата Сообщение от shchurkoroman Посмотреть сообщение
3
1 20
4 5
10 2
, высчитываете общую площадь всех листов S.
Затем сортируете листы по площади. Потом проход по листам начиная с минимальной площади. Для каждого текущего листа делаете так:
ищите в предыдущих листах, лист максимальной площади, который может поместиться на текущий лист. Если такой лист найден, то из S вычитаете его площадь, а сам такой найденный лист удаляете совсем.
По окончании прохода выводите значение S.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.06.2012, 07:04     Листы жести - минимальную площадь #10
Цитата Сообщение от shchurkoroman Посмотреть сообщение
На складе хранятся прямоугольные листы жести разных размеров. Листы расположены горизонтально на полу. Для экономии поверхности, они накладываются друг на друга, но так, чтобы лист лежащий выше, в целом размере был размещен на листе, который находится под ним. Кладовщик заботится о том, чтобы соответствующие края листов жести были параллельными, а в середины листов создавали единую стопку, лежа на одной вертикали. Чтобы приспособиться к листу жести, который находится ниже можно поворачивать его на 90 градусов вокруг центра.
Все листы сложить на самый большой.
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
07.06.2012, 22:45  [ТС]     Листы жести - минимальную площадь #11
Здравствуйте подправил задачу но все таки

для набора данных:

14
20 1
1 19
2 9
2 10
1 15
4 5
9 2
1 8
2 7
2 9
7 2
2 3
4 4
4 3

ответ 60

а программа выдает 168

Вот код программы помогите разобраться как сделать этот алгоритм

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
111
112
#include <iostream>
#include <fstream>
 
using namespace std;
 
void swap (int *a, int *b)
{
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
 
void bubblesort(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=0; j < size-i; ++j) {
            if(tab[j][1]<tab[j][0]){
                swap(&tab[j][0], &tab[j][1]);
            }
        }
    }
}
 
void bubblesort1(int tab[][2], int size)
{
    for(int i=0; i < size; ++i) {
        for(int j=1; j < size-i; ++j) {
            if(tab[j][0]*tab[j][1] > tab[j-1][0]*tab[j-1][1]) {
                swap(&tab[j][0], &tab[j-1][0]);
                swap(&tab[j][1], &tab[j-1][1]);
            }
        }
    }
}
 
int square(int tab[][2], int size)
{
    int z=0;
    int h,w;
    int square=tab[0][0]*tab[0][1];
    for(int i=1; i < size; ++i)
    {
         if (tab[i][0] <= tab[i-1][0] && tab[i][1] <= tab[i-1][1])
         {
                       
         }
         
         else
         {
         if(z==0)
         {
         square += tab[i][0]*tab[i][1];
         z=1;
         h=tab[i][0];
         w=tab[i][1];
         }
         
         if(z>0)
         {
         if (tab[i][0] <= h && tab[i][1] <= w)
         {
         h=tab[i][0];
         w=tab[i][1];             
         }
         
         else
         {
         square += tab[i][0]*tab[i][1];
         h=tab[i][0];
         w=tab[i][1];
         }   
         }
         }
    }
    return square;
}
 
int main()
{
    int n,k;
    cin>>k;
    while (k)
    {
        int rozmiar[k][2];
        for (int i=0; i<k; ++i) cin>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, k);
        bubblesort1(rozmiar, k);
        cout<<square(rozmiar, k)<<endl;
        cin>>k;
    }
 
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    in>>n;
    while (n)
    {
        int rozmiar[n][2];
        for (int i=0; i<n; ++i) in>>rozmiar[i][0]>>rozmiar[i][1];
        bubblesort(rozmiar, n);
        bubblesort1(rozmiar, n);
        out<<square(rozmiar, n)<<endl;
        in>>n;
    }
    in.close();
    out.close();
 
    return 0;
}
Помогите пожалуйста а то ума не приложу как сделать эту программу
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
07.06.2012, 22:46  [ТС]     Листы жести - минимальную площадь #12
Как решить эту проблему!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.06.2012, 23:30     Листы жести - минимальную площадь #13
пробуйте сдавать:
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
#include <iostream>
#include <fstream>
 
using namespace std;
 
 
int main()
{
    int n,i,j,s,rozmiar[200][2],pl[200],t,m;
    bool a[200];
    ifstream in("Bin.txt");
    ofstream out("Bout.txt");
    if(in == NULL)    {    
    printf (" Blad odczytu pliku Bin.txt\n");
    return 0;
    }
    while (true)
    {
        in>>n;
        if(n==0)
            break;
        s=0;
        for (i=0; i<n; ++i)
        {
            in>>rozmiar[i][0]>>rozmiar[i][1];
            a[i]=false;             
            pl[i]=rozmiar[i][0]*rozmiar[i][1];
            s+=pl[i];
        }
        for(i=0; i<n-1; i++)
        {
            m=i;
            for(j=i+1; j<n; j++)
                if(pl[m]>pl[j])
                    m=j;
            t=pl[i]; pl[i]=pl[m]; pl[m]=t;
            t=rozmiar[i][1]; rozmiar[i][1]=rozmiar[m][1]; rozmiar[m][1]=t;
            t=rozmiar[i][0]; rozmiar[i][0]=rozmiar[m][0]; rozmiar[m][0]=t;
        }
        for(i=1; i<n; i++)
        {
            t=-1;
            for(j=0; j<i; j++)
                if(((rozmiar[i][1]>=rozmiar[j][1] && rozmiar[i][0]>=rozmiar[j][0]) ||
                    (rozmiar[i][1]>=rozmiar[j][0] && rozmiar[i][0]>=rozmiar[j][1])) && !a[j])
                    t=j;    
            if(t!=-1)
            {
                s-=pl[t];
                a[t]=true;
            }
        }        
        out<<s<<endl;       
    }
    in.close();
    out.close();
 
    return 0;
}
кстати в ранее приведенных тестах есть ошибки:
Цитата Сообщение от shchurkoroman Посмотреть сообщение
12
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
7 5
9 4
0
результат должен быть
196
на самом деле результат должен быть: 171:
вот эта часть:
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
укладывается друг на друга и остается здесь только 10*10=100
+ 7*5+9*4=171
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2012, 01:42     Листы жести - минимальную площадь
Еще ссылки по теме:

C++ Найти минимальную сумму
Определить максимальную и минимальную цифру числа C++
Найти минимальную площадь прямоугольника из набора C++
C++ Массивы: определить максимальную и минимальную температуры
C++ Найти x и y и минимальную сумму x и y

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

Или воспользуйтесь поиском по форуму:
shchurkoroman
2 / 2 / 0
Регистрация: 27.03.2012
Сообщений: 13
08.06.2012, 01:42  [ТС]     Листы жести - минимальную площадь #14
Спасибо огромное! Программа работает идеально)
Yandex
Объявления
08.06.2012, 01:42     Листы жести - минимальную площадь
Ответ Создать тему
Опции темы

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