Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int sMax = 0, // Суммарная площадь всех прямоугольников.
- debug = 0; // 1 = отладка
- void comb_sorting(int *a, int size);
- int search(int *p, int);
- void init(int &N, int *p);
- void monitor(int *p, int n);
- ///////////////////////////////////////////////// sizeof(int) * //nArr[100000],
- int main() //
- {
- int *nArr = new int[1000000]; // 0000
- int N,
- s = 0,
- n = 0,
- nCounter = 0,
- *p = nArr,
- i = 0,
- remainder ;
- if(debug == 0)
- {
- cin >> N;
- for(i = 0; i < N; i++) cin >> nArr[i];
- }
- else init(N, nArr);
- remainder = N;
- comb_sorting(nArr, N);
- if(debug) monitor(nArr, N);
- ///////////////////////
- while(remainder > 3)
- {
- i = search(p, remainder);
- remainder -= i;
- p += i;
- if(debug) cout << ", bias = " << i << ", remainder = "<< remainder << endl;
- }
- cout << sMax;
- delete []nArr;
- return 0;
- }
- // Инициализация массива для тестирования
- /////////////////////////////////////////////////
- void init(int &N, int *p) //
- {
- N = 12; int a[99] = {4, 2, 5, 3, 7, 10, 11, 9, 9, 20, 20, 20};
- //N = 8; int a[99] = {7, 3, 4, 8, 10, 11, 20, 20};
- for(int i = 0; i < N; i++) p[i] = a[i];
- }
- // Возвращает смещение в массиве (кол-во элементов), относительно старта поиска отрезков.
- ///////////////////////////////////////////////////////
- int search(int *p, int remainder) //
- {
- int L1 = 0,
- L2 = 0,
- i = 0,
- Res = 0;
- do
- { if(p[i] == p[i+1]) L1 = p[i] ;
- else if(p[i]-1 == p[i+1]) L1 = p[i] - 1;
- p++; Res++; if(remainder <= Res) return Res;
- } while(L1 == 0);
- if(debug) cout << "L1 = " << L1;
- p++; Res++;
- do
- { if(p[i] == p[i+1]) L2 = p[i] ;
- else if(p[i]-1 == p[i+1]) L2 = p[i] - 1;
- p++; Res++; if(remainder <= Res) return Res;
- } while(L2 == 0);
- if(debug) cout << ", L2 = " << L2;
- p++; Res++;
- sMax += L1 * L2; // if(debug) cout << "sMax = " << sMax << endl;
- return Res;
- }
- // Меняет местами содержимое двух переменных
- //////////////////////////////////////////////////////
- void swap(int &a, int &b) //
- {
- int buf = a;
- a = b;
- b = buf;
- }
- // Сортировка "Расчёска"
- /////////////////////////////////////////////////////
- void comb_sorting(int *a, int size) // Передаёте адрес элемента массива,
- { // с которого начинаете упорядочивание по возрастанию.
- // И передаёте кол-во элементов, которые будут отсортированы.
- int step = size - 1;
- while(step >= 1)
- {
- for(int i = 0; i + step < size; i++)
- {
- if(a[i] < a[i+step])
- {
- swap(a[i], a[i+step]);
- } //
- }
- step /= 1.2473309;
- }
- }
- //
- /////////////////////////////////////////////////
- void monitor(int *p, int n) //
- {
- for(int i = 0; i < n; i++)
- {
- cout << p[i] << ", ";
- } cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement