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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//サンタ服
/**
題目:
設一蛋糕長闊高分別為X,Y,Z cm,以刀子從上方垂直切下分割蛋糕,求不同條件下最小蛋糕的體積(cm^3)

輸入形式:
X Y Z N
d_1 a_1
d_2 a_2
...
d_N a_N

X,Y,Z分別為長闊高,N是共計下刀數
d_i a_i分別為下刀方向和下刀位置
d_i=0,代表下刀方向與Y成平行,此時a_i則代表距離左側面多少cm
d_i=1,代表下刀方向與X成平行,此時a_i則代表距離前面多少cm

條件:
1<=X,Y,Z,N<=100
d_i= 0 or 1
1<=a_i<=X-1(d_i=0) or Y-1(d_i=1)
同一位置只能下刀一次
輸入數值全為正整數

解題思路:
可不考慮Z,因為不會切到X方向
題目可簡化為尋找最小面積 -> 即找最小x與最小y
**/

#include <iostream>

using namespace std;

struct Cake {
    int x, y, z, cut;
} cake;

struct Cut {
    int* cut = nullptr;
    int count = 0;
} cut_x, cut_y;

void create_cake(Cake& arg0) {
    string buffer, temp;
    int count = 1;
    
    getline(cin, buffer);
    for (auto it=buffer.begin(); it!=buffer.end(); it++) {
        if (*it==' ') {
            switch(count++) {
            case 1:
                arg0.x = stoi(temp, nullptr);
                break;
            case 2:
                arg0.y = stoi(temp, nullptr);
                break;
            case 3:
                arg0.z = stoi(temp, nullptr);
                break;
            }
            temp = "";
        } else {
            temp += *it;
        }
    }
    arg0.cut = stoi(temp, nullptr);
}

void cut_cake(Cut& x, Cut& y, const Cake& arg0) {
    int* temp_x = new int[arg0.cut];
    int* temp_y = new int[arg0.cut];
    
    string buffer, temp;
    
    for (int i=0; i<arg0.cut; i++) {
        getline(cin, buffer);
        for (auto it=buffer.begin()+2; it!=buffer.end(); it++) {
            temp += *it;
        }
    
        if (buffer[0]=='0') {
            temp_x[x.count++] = stoi(temp, nullptr);
        } else {
            temp_y[y.count++] = stoi(temp, nullptr);
        }
        temp = "";
    }
    
    if (x.count == 0) {
        x.cut = nullptr;
    } else {
        x.cut = new int[x.count];
        for (int i=0; i<x.count; i++) {
            x.cut[i] = temp_x[i];
        }
    }
    
    if (y.count == 0) {
        y.cut = nullptr;
    } else {
        y.cut = new int[y.count];
        for (int i=0; i<y.count; i++) {
            y.cut[i] = temp_y[i];
        }
    }
    
    delete[] temp_x;
    delete[] temp_y;
}

void quick_sort(Cut& arg0, const int& left, const int& right) {
    int i = left;
    int j = right-1;
    int tmp;
    int pivot = arg0.cut[(left + right)/2];

    while (i <= j) {
        while (arg0.cut[i] < pivot)
            i++;
        while (arg0.cut[j] > pivot)
            j--;
        if (i <= j) {
            tmp = arg0.cut[i];
            arg0.cut[i] = arg0.cut[j];
            arg0.cut[j] = tmp;
            i++;
            j--;
        }
    };

    if (left < j)
        quick_sort(arg0, left, j);
    if (i < right)
        quick_sort(arg0, i, right);
}

int find_smallest_side(Cut& arg0, const int& boundary) {
    if (arg0.cut == nullptr) return boundary;

    quick_sort(arg0, 0, arg0.count);
    int min = arg0.cut[0];
    for (int i=1; i<arg0.count; i++) {
        if (min > arg0.cut[i]-arg0.cut[i-1])
            min = arg0.cut[i]-arg0.cut[i-1];
    }
    
    if (min > boundary-arg0.cut[arg0.count-1])
        min = boundary-arg0.cut[arg0.count-1];
        
    return min;
}

int find_smallest_piece(Cut& x, Cut& y, const Cake& arg0) {
    int min_x, min_y;
    
    if (arg0.x == 1)
        min_x = 1;
    else
        min_x = find_smallest_side(x, arg0.x);
        
    if (arg0.y == 1)
        min_y = 1;
    else
        min_y = find_smallest_side(y, arg0.y);
    
    return (min_x*min_y*arg0.z);
}

int main() {
    create_cake(cake);
    cut_cake(cut_x, cut_y, cake);
    cout << find_smallest_piece(cut_x, cut_y, cake);
    
    return 0;
}