Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

爆搜过了

Posted by KatrineYang at 2016-08-21 05:40:58 on Problem 1169
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator