网易c++笔试牛牛分田问题

//题目描述：牛牛和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说明语句没有删除，但是结果应该是正确的，程序还打印输出切割方法，感兴趣的大家可以看一下。

你这ac了没？

我的想法是，把输入的矩阵一步步变成4*4的。 如果矩阵行数大于4，就寻找价值最小的那一点，将它所在那一行和它上面一行或者下面一行对应列数相加（看最小点上面的点价值小还是下面的点价值小，还要考虑最小点在第一行和最后一行的情况），处理后矩阵从N*M变为(N-1)*M； 如果矩阵的列数大于4，就寻找价值最小的那一点，将它所在那一列和它左边一列或者右边一列对应行数相加，处理后矩阵从N*M变为N*(M-1)。 如果上面两步处理后的矩阵还是大于4*4，则继续处理。 矩阵变成4*4后，价值最小的那一点的价值即为结果。 不知道这个思路有没有漏洞。 我提交的答案忘了处理最小值在第一行或者最后一行和第一列和最后一列的情况，导致会报异常，所以没有AC。

是在线下做的。。http://blog.csdn.net/lsxpu/article/details/52100370