Untitled

By: a guest on Jul 14th, 2012  |  syntax: None  |  size: 2.96 KB  |  hits: 14  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. array median transformation minimum steps
2. #include <cstdio>
3. #include <iostream>
4. using namespace std;
5.
6. int bc[1<<15];
7. const int M = (1<<15) - 1;
8.
9. void setMin(int& ret, int c)
10. {
11.     if(c < ret) ret = c;
12. }
13.
14. void doit(int n, int mask, int currentSteps, int& currentBest)
15. {
17.     if(numMax == n) {
18.         setMin(currentBest, currentSteps);
19.         return;
20.     }
21.     if(currentSteps + 1 >= currentBest)
22.         return;
23.     if(currentSteps + 2 >= currentBest)
24.     {
25.         if(numMax * 2 >= n) {
26.             setMin(currentBest, 1 + currentSteps);
27.         }
28.         return;
29.     }
30.
31.     if(numMax < (1<<currentSteps)) return;
32.
33.     for(int i=0;i<n;i++)
34.     {
35.         int a = 0, b = 0;
37.         for(int j=i;j<n;j++)
38.         {
39.             c |= (1<<j);
41.             else a++;
42.             if(b >= a) {
43.                 doit(n, c, currentSteps + 1, currentBest);
44.             }
45.         }
46.     }
47. }
48.
49. int v[32];
50. void solveCase() {
51.     int n;
52.     scanf(" %d", &n);
53.     int maxElement = 0;
54.     for(int i=0;i<n;i++) {
55.         scanf(" %d", v+i);
56.         if(v[i] > maxElement) maxElement = v[i];
57.     }
59.     for(int i=0;i<n;i++) if(v[i] == maxElement) mask |= (1<<i);
60.     int ret = 0, p = 1;
61.     while(p < n) {
62.         ret++;
63.         p *= 2;
64.     }
66.     printf("%dn",ret);
67. }
68.
69. main() {
70.     for(int i=0;i<(1<<15);i++) {
71.         bc[i] = bc[i>>1] + (i&1);
72.     }
73.     int cases;
74.     scanf(" %d",&cases);
75.     while(cases--) solveCase();
76. }
77.
78. [6 1 5 9 3 2 0 7 4 8]
79.
80. [6 1 5 9 9 2 0 7 4 8]
81.
82. [6 9 9 9 9 2 0 7 4 8]
83.
84. [9 9 9 9 9 9 9 9 4 8]
85.
86. [9 9 9 9 9 9 9 9 9 9]
87.
88. For each group of consecutive maximal elements in original array:
89.   Mark corresponding element in the matrix and clear other elements
90.   For each matrix diagonal, starting with one, containing this element:
91.     For each marked element in this diagonal:
92.       Retrieve current number of turns from this matrix element
93.       (use indexes of this matrix element to initialize p1 and p2)
94.       p2 = end of the group
95.       p1 = start of the group
96.       Decrease p1 while it is possible to keep median at maximum value
97.       (now all values between p1 and p2 are assumed as maximal)
98.       While p2 < N:
99.         Check if number of maximal elements in the array is >= N/2
100.           If this is true, compare current number of turns with the best result
101.                and update it if necessary
102.           (additional matrix with number of maximal values between each pair of
103.             points may be used to count elements to the left of p1 and to the
104.             right of p2)
105.         Look at position [p1, p2] in the matrix. Mark it and if it contains
106.             larger number of turns, update it
107.         Repeat:
108.           Increase p1 while it points to maximal value
109.           Increment p1 (to skip one non-maximum value)
110.           Increase p2 while it is possible to keep median at maximum value
111.         while median is not at maximum value