//题目描述：牛牛和15个朋友玩打土豪分田地的游戏，牛牛决定让你来分田地， // 地主的土地可以看成是一个矩形，每个位置有一个价值。分割田地 // 的方法是横竖各切3刀，分成16分，牛牛作为领导干部，总是选择总 // 价值最小的一份田地，你作为牛牛最好的朋友，希望他分得的土地 // 的价值和尽可能大，你知道这个值最大是多少吗？ //输入：每个输入包含一个测试用例，第一行包含两个整数n和m，表示矩阵的大小， // 接下来n行每行包含m个0到9的数字，代表每块位置的价值 //输出：输出一行表示牛牛能分得田地的最大值 //题目来源：网易内推c++笔试第三道编程题 #include <iostream> #include <vector> #include <algorithm> using namespace std; int compute_sum(const vector<vector<int> >& A,int a, int b, int c, int d)//左上角坐标(a,c)，右下角坐标(b,d) { int sum = 0; for (int i =a ; i <= b; ++i) { for (int j = c; j <= d; ++j) { sum+=A[i][j]; } } return sum; } int max_index(vector<int>& temp)//返回数组中最大元素对应的索引/下标 { int k = 0; int max = temp[0]; for (int i = 1; i < temp.size(); ++i) { if (temp[i]>max) { max = temp[i]; k = i; } } return k; } int get_min(vector<int>& temp)//返回数组中最小元素 { int min = temp[0]; for (int i = 1; i < temp.size(); ++i) { if (temp[i]<min) { min = temp[i]; } } return min; } int get_max(vector<int>& temp)//返回数组中最大元素 { int max = temp[0]; for (int i = 1; i < temp.size(); ++i) { if (temp[i]>max) { max = temp[i]; } } return max; } int X_cut(const vector<vector<int> >& A, vector<int>& X_num, const int& a)//水平方向下刀函数 { int min = 0; int max = 0; vector<int> temp; vector<int> sum;//记录每个块的总价值 int top = 0;//记录子块的起始行号 int tail = 0;//记录子块的末尾行号 cout << "初始长度=" << X_num.size() << endl; if (X_num.size() == 0) { for (int pos = 0; pos <A.size() - 1; ++pos)//切口位置pos的取值范围是[0, A.size() - 2] { sum.push_back(compute_sum(A, 0, pos, 0, A[0].size() - 1)); sum.push_back(compute_sum(A, pos + 1, A.size() - 1, 0, A[0].size() - 1)); min = (sum[0] <= sum[1]) ? sum[0] : sum[1]; cout << "min=" << min << endl; temp.push_back(min); sum.clear(); } X_num.push_back(max_index(temp)); cout <<endl<<endl; if (X_num.size() == a) { int max_min = get_max(temp); return max_min; } temp.clear(); } int flag = 0; while (X_num.size() != a) { for (int pos = 0; pos < A.size() - 1; ++pos) { flag = 0; for (int i = 0; i < X_num.size(); ++i) { if (pos == X_num[i]) { flag = 1; } } if (flag == 1) temp.push_back(0);//将旧位置标记为0,便于查找合适的切口 if (flag == 0)//表示目标切口位置是新位置 { vector<int> temp2(X_num); temp2.push_back(pos); sort(temp2.begin(), temp2.end()); top = 0; tail = temp2[0]; sum.push_back(compute_sum(A, top, tail, 0, A[0].size() - 1)); for (int i = 0; i < temp2.size() - 1; ++i) { top = temp2[i] + 1; tail = temp2[i + 1]; sum.push_back(compute_sum(A, top, tail , 0, A[0].size() - 1)); } top = temp2[temp2.size() - 1] + 1; tail = A.size() - 1; sum.push_back(compute_sum(A, top, tail, 0, A[0].size() - 1)); int min = get_min(sum); temp.push_back(min); cout << "min=" << min << endl; temp2.clear(); sum.clear(); } } X_num.push_back(max_index(temp)); cout << endl<<endl; if (X_num.size() == a) { int max_min = get_max(temp); return max_min; } else { temp.clear(); } } } int Y_cut(const vector<vector<int> >& A, const vector<int>& X_num,vector<int>& Y_num,int b)//竖直方向下刀函数 { int min = 0; int max = 0; vector<int> temp; vector<int> sum;//记录每个块的总价值 int top = 0;//记录子块的起始列号 int tail = 0;//记录子块的末尾列号 cout << "初始长度=" << Y_num.size() << endl; vector<int> temp3(X_num); sort(temp3.begin(),temp3.end()); if (Y_num.size() == 0) { for (int pos = 0; pos <A[0].size() - 1; ++pos)//切口位置pos的取值范围是[0, A[0].size() - 2] { top = 0; tail = temp3[0]; sum.push_back(compute_sum(A, top, tail, 0, pos)); sum.push_back(compute_sum(A, top, tail, pos+1, A[0].size() - 1)); for (int i = 0; i < temp3.size() - 1; ++i) { top = temp3[i] + 1; tail = temp3[i + 1]; sum.push_back(compute_sum(A, top, tail , 0, pos)); sum.push_back(compute_sum(A, top, tail, pos+1, A[0].size() - 1)); } top = temp3[temp3.size() - 1] + 1; tail = A.size() - 1; sum.push_back(compute_sum(A, top, tail, 0, pos)); sum.push_back(compute_sum(A, top, tail, pos+1, A[0].size() - 1)); min = get_min(sum); temp.push_back(min); cout << "min=" << min << endl; sum.clear(); } Y_num.push_back(max_index(temp)); cout <<endl<<endl; if (Y_num.size() == b) { int max_min = get_max(temp); return max_min; } temp.clear(); } int flag = 0; while (Y_num.size() != b) { for (int pos = 0; pos < A[0].size() - 1; ++pos) { flag = 0; for (int i = 0; i < Y_num.size(); ++i) { if (pos == Y_num[i]) { flag = 1; } } if (flag == 1) temp.push_back(0);//将旧位置标记为0,便于查找合适的切口 if (flag == 0)//表示目标切口位置是新位置 { vector<int> temp4(Y_num); temp4.push_back(pos); sort(temp4.begin(), temp4.end()); sum.push_back(compute_sum(A, 0, temp3[0], 0,temp4[0] )); for (int i = 0; i < temp3.size() - 1; ++i) { sum.push_back(compute_sum(A,temp3[i] + 1 ,temp3[i + 1] , 0,temp4[0] )); } sum.push_back(compute_sum(A,temp3[temp3.size() - 1] + 1 ,A.size() - 1 , 0, temp4[0])); for (int j = 0; j < temp4.size() - 1; ++j) { top = temp4[j] + 1; tail = temp4[j + 1]; sum.push_back(compute_sum(A, 0, temp3[0], top,tail )); for (int i = 0; i < temp3.size() - 1; ++i) { sum.push_back(compute_sum(A,temp3[i] + 1 ,temp3[i + 1] , top,tail )); } sum.push_back(compute_sum(A,temp3[temp3.size() - 1] + 1 ,A.size() - 1 , top, tail)); } sum.push_back(compute_sum(A, 0, temp3[0],temp4[temp4.size() - 1] + 1 , A[0].size()-1)); for (int i = 0; i < temp3.size() - 1; ++i) { sum.push_back(compute_sum(A, temp3[i] + 1, temp3[i + 1], temp4[temp4.size() - 1] + 1, A[0].size()-1)); } sum.push_back(compute_sum(A, temp3[temp3.size() - 1] + 1, A.size() - 1, temp4[temp4.size() - 1] + 1, A[0].size()-1)); min=get_min(sum); temp.push_back(min); cout << "min=" << min<< endl; temp4.clear(); sum.clear(); } } Y_num.push_back(max_index(temp)); cout << endl<<endl; if (Y_num.size() == b) { int max_min = get_max(temp); return max_min; } else { temp.clear(); } } } int main() { int n = 0; cout << "请输入矩阵的行数n" << endl; cin >> n; //矩阵行数 int m = 0; cout << "请输入矩阵的列数m" << endl; cin >> m; //矩阵列数 int a = 0; cout << "请输入水平方向需要切的刀数a, a的范围[1,n)" << endl; //a的范围[1,n) cin >> a; //水平方向需要切的刀数 int b = 0; cout << "请输入竖直方向需要切的刀数b, b的范围[1,m)" << endl; //b的范围[1,m) cin >> b; //竖直方向需要切的刀数 vector<vector<int> > A(n); //二维数组来保存矩阵 for (int i = 0; i < n; i++) { A[i].resize(m); } cout << "请以矩阵的形式输入矩阵" << endl; for (int i = 0; i < n; ++i) //初始化二维数组 { for (int j = 0; j < m; ++j) { cin >> A[i][j]; } } cout << "输入的二维数组为" << endl; for (int i = 0; i < n; ++i) //初始化二维数组 { for (int j = 0; j < m; ++j) { cout << " " << A[i][j]; } cout << endl; } vector<int> X_num;//存储水平方向下刀位置 int value=X_cut(A, X_num, a); cout << endl << endl; cout << "下面依次输出水平方向下刀位置" << endl; for (int i = 0; i < X_num.size(); ++i) { cout <<" "<< X_num[i]; } cout << endl << endl << "value=" << value << endl << endl; vector<int> Y_num;//存储竖直方向下刀位置 int value2 = Y_cut(A, X_num,Y_num, b); cout << endl << endl; cout << "下面依次输出竖直方向下刀位置" << endl; for (int i = 0; i < Y_num.size(); ++i) { cout << " " << Y_num[i]; } cout << endl << endl << "value2=" << value2 << endl << endl; cout << "最小的块可能取得的最大值为" << value2 << endl << endl; return 0; } 笔试的时候题目没有看明白，回头想了想，在vs上写出来了，花了不少时间，编译运行成功。因为在VS2013上写的，有一些简单的cout说明语句没有删除，但是结果应该是正确的，程序还打印输出切割方法，感兴趣的大家可以看一下。