| ||||||||||
| 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