Advertisement
dllbridge

Untitled

Oct 9th, 2024
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.35 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. using namespace std;
  4.  
  5.  
  6. int sMax     = 0,   //  Суммарная площадь всех прямоугольников.
  7.     debug    = 0;   //  1 = отладка
  8.  
  9. void comb_sorting(int *a, int size);  
  10.  
  11. int search(int *p, int);
  12.  
  13.  
  14. void init(int &N, int *p);
  15.  
  16. void monitor(int *p, int n);
  17.  
  18.  
  19.  
  20. /////////////////////////////////////////////////                                      sizeof(int) * //nArr[100000],
  21. int main()                                     //  
  22. {
  23.    
  24.     int *nArr = new int[1000000];   //  0000
  25.    
  26.     int N,
  27.         s        = 0,    
  28.         n        = 0,
  29.         nCounter = 0,
  30.        *p        = nArr,
  31.         i        = 0,
  32.         remainder   ;
  33.        
  34.    
  35.    
  36.     if(debug   == 0)
  37.     {
  38.         cin >> N;
  39.        
  40.         for(i = 0; i < N; i++)   cin >> nArr[i];
  41.     }
  42.     else init(N, nArr);
  43.    
  44.     remainder = N;
  45.    
  46.     comb_sorting(nArr, N);
  47.    
  48.    
  49.     if(debug) monitor(nArr, N);
  50.     ///////////////////////
  51.  
  52.     while(remainder > 3)
  53.     {
  54.           i = search(p, remainder);
  55.                         remainder -= i;
  56.           p += i;
  57.           if(debug) cout << ", bias = " << i << ", remainder = "<< remainder << endl;    
  58.     }
  59.    
  60.     cout << sMax;
  61.    
  62.     delete []nArr;
  63.    
  64. return 0;
  65. }
  66.  
  67.  
  68. //  Инициализация массива для тестирования
  69. /////////////////////////////////////////////////
  70. void init(int &N, int *p)                      //
  71. {
  72.      
  73.      N = 12;  int a[99] = {4, 2, 5, 3, 7, 10, 11, 9, 9, 20, 20, 20};
  74.      
  75.      //N = 8;  int a[99] = {7, 3, 4, 8, 10, 11, 20, 20};
  76.      
  77.      for(int i = 0; i < N; i++) p[i] = a[i];
  78. }
  79.  
  80.  
  81. //  Возвращает смещение в массиве (кол-во элементов), относительно старта поиска отрезков.
  82. ///////////////////////////////////////////////////////
  83. int search(int *p, int remainder)                                   //
  84. {
  85.  
  86.     int L1     = 0,
  87.         L2     = 0,
  88.         i      = 0,
  89.         Res    = 0;
  90.    
  91.     do            
  92.     {         if(p[i]   == p[i+1])  L1 = p[i]    ;  
  93.         else  if(p[i]-1 == p[i+1])  L1 = p[i] - 1;  
  94.                
  95.         p++;  Res++;    if(remainder <= Res) return Res;    
  96.        
  97.     }   while(L1 == 0);  
  98.    
  99.         if(debug) cout << "L1 = " << L1;
  100.    
  101.         p++;  Res++;  
  102.  
  103.     do            
  104.     {         if(p[i]   == p[i+1])  L2 = p[i]    ;  
  105.         else  if(p[i]-1 == p[i+1])  L2 = p[i] - 1;  
  106.                
  107.         p++;  Res++;    if(remainder <=  Res) return Res;    
  108.        
  109.     }   while(L2 == 0);    
  110.    
  111.         if(debug) cout << ", L2 = " << L2;  
  112.         p++;  Res++;
  113.    
  114.     sMax += L1 * L2;     // if(debug)  cout << "sMax = " << sMax << endl;
  115.  
  116. return  Res;       
  117. }
  118.  
  119.  
  120. //           Меняет местами содержимое двух переменных
  121. //////////////////////////////////////////////////////                      
  122. void swap(int &a, int &b)                           //
  123. {
  124.    
  125.      int buf = a;
  126.      a = b;
  127.      b = buf;
  128. }
  129.  
  130.  
  131.  
  132. //                              Сортировка "Расчёска"
  133. /////////////////////////////////////////////////////                                            
  134. void comb_sorting(int *a, int size)                //                                Передаёте адрес элемента массива,
  135. {                                                  //              с которого начинаете упорядочивание по возрастанию.
  136.                                                    //       И передаёте кол-во элементов, которые будут отсортированы.
  137.      int step = size - 1;
  138.  
  139.      while(step >= 1)
  140.      {
  141.            
  142.          for(int i = 0; i + step < size; i++)      
  143.          {
  144.                    
  145.              if(a[i] < a[i+step])  
  146.              {
  147.                 swap(a[i], a[i+step]);    
  148.              }                                     //  
  149.          }  
  150.          
  151.          step /= 1.2473309;
  152.      }      
  153. }
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161. //  
  162. /////////////////////////////////////////////////
  163. void monitor(int *p, int n)                    //  
  164. {
  165.      
  166.      for(int i = 0; i < n; i++)
  167.      {
  168.              
  169.          cout << p[i] << ", ";        
  170.      }   cout << endl;
  171.      
  172. }
  173.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement