蓝桥杯 最大获利 模拟

问题描述

　　Chakra是一位年轻有为的企业家，最近他在进军餐饮行业。他在各地开拓市场，共买下了N个饭店。在初期的市场调研中，他将一天划分为M个时间段，并且知道第i个饭店在第j个时间段内，会有Aij位服务员当值和Bij位客户光临。他还分析了不同饭店不同时间段客户的需求，得到第i个饭店在第j个时间段内，平均每位客户消费Cij元。为了创设品牌形象，Chakra决定每个饭店每天只选择一个时间段营业，每个服务员至多接待一位顾客（若顾客数多于服务员数，超过部分的顾客当天就无法在该店消费了）。
　　企业家的目的终究还是获利。请你安排营业时间，并告诉Chakra每天消费总额最多为多少。

输入格式

　　第一行两个整数，N、M。
　　第二行开始依次给出三个矩阵A(N*M)、B(N*M)、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

解题思路：读懂题意就很容易了，数据范围最大值为100*5000*10^9 = 5 * 10^14，用 long long 存储。

普通做法：

#include <bits/stdc++.h>
using namespace std;
long long a[105][105], b[105][105], c[105][105];
int main() {
    int n, m;
    cin >> n >> m;
    //a数组输入服务员信息 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    //b数组输入顾客信息 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> b[i][j];
        }
    }
    //c数组输入顾客营业额信息 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
        }
    }
    //对于a数组和b数组，每一位上取营业员数和顾客数量的最小值，作为成功提供营业的数量
    /*
        样例分析：a数组为： 1 2 3
                        3 2 1
                b数组为： 3 2 1
                        1 2 3
        每一位上取营业员数和顾客数量的最小值
        所以成功提供营业的数量数组d：
                d数组为： 1 2 1
                        1 2 1                        
                c数组为： 4 5 2
                        3 1 6 
        把d数组依次乘以c数组得出答案营业额数组e ：
                e数组为 ：4 10 2
                        3  2 6 
        分析e数组，样例是2个饭店，3个时间段
                第一个饭店在第一个时间段的营业额是4 
                第一个饭店在第二个时间段的营业额是10
                第一个饭店在第三个时间段的营业额是2
                第二个饭店在第一个时间段的营业额是3
                第二个饭店在第二个时间段的营业额是2
                第二个饭店在第三个时间段的营业额是6
                所以最终答案为10+6=16 
    */ 
    for (int i = 0; i < n; i++) { //在a数组和b数组每一位中选出最小值乘以c数组 
        for (int j = 0; j < m; j++) {
            if (a[i][j] > b[i][j]) {
                c[i][j] *= b[i][j];
            } else { 
                c[i][j] *= a[i][j];
            }
        }
    } //现在c数组的值即为营业额数组，数值同上面e数组 
    /*for (int i = 0; i < n; i++) { 
        for (int j = 0; j < m; j++) {
            cout << c[i][j] << " "; 
        }
        cout << endl;
    }*/
    for (int i = 0; i < n; i++) { //对二维数组每一行进行冒泡排序 
        for (int k = 0; k < m; k++) {
            for (int j = 0; j < m - k - 1; j++) {
                if (c[i][j] > c[i][j + 1]) {
                    swap(c[i][j], c[i][j + 1]);
                }
            }
        }
    }
    /*for (int i = 0; i < n; i++) { 
        for (int j = 0; j < m; j++) {
            cout << c[i][j] << " "; 
        }
        cout << endl;
    }*/
    //排序后，现在c数组内的值为：2 4 10
    //                     2 3 6 
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        ans += c[i][m - 1]; //加10，加6 
    }
    cout << ans << endl;
    return 0;
}

也可以只开一个数组：

#include <bits/stdc++.h>
using namespace std;
long long a[105][105];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    long long t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            a[i][j] = min(a[i][j], t);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            a[i][j] *= t;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            for (int j = 0; j < m - k - 1; j++) {
                if (a[i][j] > a[i][j + 1]) {
                    swap(a[i][j], a[i][j + 1]);
                }
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        ans += a[i][m - 1]; 
    }
    cout << ans << endl;
    return 0;
}

 顺便复习下冒泡排序：

#include <bits/stdc++.h>
using namespace std;
int a[10];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}