Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
爆搜过了#include <iostream> #include <vector> using namespace std; void quickSort(vector<int> &s, int l, int r) { if (l< r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); // 递归调用 quickSort(s, i + 1, r); } } int perm[24][4] = {{1,2,3,4}, {1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}, {1,4,3,2}, {2,1,3,4}, {2,1,4,3}, {2,3,1,4}, {2,3,4,1}, {2,4,1,3}, {2,4,3,1}, {3,1,2,4}, {3,1,4,2}, {3,2,1,4}, {3,2,4,1}, {3,4,1,2}, {3,4,2,1}, {4,1,2,3}, {4,1,3,2}, {4,2,1,3}, {4,2,3,1}, {4,3,1,2}, {4,3,2,1}}; int lw[2][2] = {{0,1},{1,0}}; int mx(int a, int b){ return (a>b) ? a : b; } int mn(int a, int b){ return (a<b) ? a : b; } vector<int> ans; int minV = 2147483647; void gx(int tempW, int tempL){ int tempAns = tempW * tempL; if(tempAns > minV) return; if(tempAns < minV){ minV = tempAns; ans.clear(); ans.push_back(mn(tempW, tempL)); return; } ans.push_back(mn(tempW, tempL)); } int main() { int len[4][2]; for(int i = 0; i < 4; i++){ for(int j = 0; j < 2; j++){ cin >> len[i][j]; } } for(int i = 0; i < 24; i++){ for(int j = 0; j < 16; j++){ int bits[4]; for(int k = 0; k < 4; k++){ bits[k] = ((j & (1<<k)) > 0) ? 1 : 0; } int l[5], w[5]; for(int k = 1; k <= 4; k++){ l[k] = len[perm[i][k-1]-1][lw[bits[k-1]][0]]; w[k] = len[perm[i][k-1]-1][lw[bits[k-1]][1]]; } int tmpW, tmpL; //1 tmpW = w[1]+w[2]+w[3]+w[4]; tmpL = mx(l[1], mx(l[2], mx(l[3], l[4]))); gx(tmpW, tmpL); //2 tmpW = mx(l[1], mx(l[2], l[3])) + l[4]; tmpL = mx(w[4], w[1]+w[2]+w[3]); gx(tmpW, tmpL); //3 tmpW = mx(l[4], mx(l[1], l[2]) + l[3]); tmpL = w[4] + mx(w[1]+w[2], w[3]); gx(tmpW, tmpL); //4 tmpW = mx(l[1]+l[2], mx(l[3], l[4])); tmpL = mx(w[1], w[2]) + w[3] + w[4]; gx(tmpW, tmpL); if(w[1]+w[4] <= w[2]+w[3] && l[2] <= l[3]){ if(w[1] <= w[2]){ tmpW = mx(l[1]+l[2], l[3]+l[4]); tmpL = w[2]+w[3]; gx(tmpW, tmpL); } else{ tmpW = l[3] + mx(l[1], l[4]); tmpL = w[2] + w[3]; gx(tmpW, tmpL); tmpW = mx(l[1]+l[2], l[3]+l[4]); tmpL = w[1]+w[3]; gx(tmpW, tmpL); } } } } quickSort(ans, 0, ans.size()-1); cout << minV << endl; int l = -1; for(int i = 0; i < ans.size(); i++){ if(ans[i] == l) continue; cout << ans[i] << " " << minV/ans[i] << endl; l = ans[i]; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator