试题 算法训练 最大获利（易懂方案）

试题 算法训练 最大获利

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　Chakra是一位年轻有为的企业家，最近他在进军餐饮行业。他在各地开拓市场，共买下了N个饭店。在初期的市场调研中，他将一天划分为M个时间段，并且知道第i个饭店在第j个时间段内，会有Aij位服务员当值和Bij位客户光临。他还分析了不同饭店不同时间段客户的需求，得到第i个饭店在第j个时间段内，平均每位客户消费Cij元。为了创设品牌形象，Chakra决定每个饭店每天只选择一个时间段营业，每个服务员至多接待一位顾客（若顾客数多于服务员数，超过部分的顾客当天就无法在该店消费了）。
　　企业家的目的终究还是获利。请你安排营业时间，并告诉Chakra每天消费总额最多为多少。
输入格式
　　第一行两个整数，N、M。
　　第二行开始依次给出三个矩阵A(NM)、B(NM)、C(N*M)。
输出格式
　　一行一个整数，最大消费总额。
样例输入
2 3
1 2 3
3 2 1
3 2 1
1 2 3
4 5 2
3 1 6
样例输出
16
数据规模和约定
　　1 <= M,N <= 100
　　1 <= Aij, Bij <= 5000
　　0 <= Cij <= 10^9

分析：我们最终的目的是:告诉Chakra每天消费总额最多为多少?我们读懂题就很简单，我一开始也是不懂，（我算成一天的总额去了）实际上是，每个饭店的每个时段，找出那个最大的消费那个时段，然后在相加每个饭店，这就是最大的消费总额了呗。

方法：我们要知道的是，如果服务员多了，顾客少的话，那么是用顾客的人数去乘以那个时间段的平均消费，如果服务员少了，顾客多的话，那么是用服务员的人数去乘以那个时间段的平均消费，我们通过for循环找出小的那个，并乘以那个时间段平均消费，最后找出每个饭店的最大消费时间段相加就是了。

附上代码：

#include<iostream>
using namespace std;
int main()
{
	/*	输入格式
		第一行两个整数，N、M。
		第二行开始依次给出三个矩阵A(N * M)、B(N * M)、C(N * M)。
	*/
	int n, m;
	int  a[100][100];//每个饭店的服务人员
	int  b[100][100];//顾客
  long long	 int  c[100][100];//平均消费
	
     cin>> n >> m;
	 
//输入每个饭店和时间段的服务员
	 for(int i=0;i<n;i++)
		 for (int j = 0; j < m; j++)
		 {
			 cin >> a[i][j];
		 }
	 //顾客
	 for (int i = 0; i < n; i++)
		 for (int j = 0; j < m; j++)
		 {
			 cin >> b[i][j];
		 }
	 //平均消费
	 for (int i = 0; i < n; i++)
		 for (int j = 0; j < m; j++)
		 {
			 cin >> c[i][j];

		 }
	 //开始比较，将人数少的用于乘平均消费
	 for (int i = 0; i < n; i++)
	 {
		 for (int j = 0; j < m; j++)
		 {//服务员少
			 if (a[i][j] < b[i][j])
			 {
				 c[i][j]= a[i][j] * c[i][j];
			 }
			 //顾客少
			 else 
			 {
				 c[i][j]= b[i][j] * c[i][j];
			 }
		 }
	 }

	 //将每个店的最大消费时刻相加
	 long long sum = 0;//sum是每家店每个时刻的最大值的总和
	 for (int i = 0; i < n; i++)
	 {
		 for (int j = 1; j < m; j++)
		 {
			 if (c[i][0] < c[i][j])
			 {//目的是让c[i][0]最后为最大时刻的值
				 c[i][0] = c[i][j];
			 }
			
		 }
		 sum += c[i][0];
	 }
	 //输出最大消费总额
	 cout <<sum<<endl;
	return 0;
}

运行结果：