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; } |
Direct link: https://paste.plurk.com/show/2329482