0021-0022：华为OD机考：消耗资源总数-数组合并

消耗资源总数—样例通过85%

题目描述

在通信系统中有一个常见的问题是对用户进行不同策略的调度

会得到不同系统消耗的性能

假设由N个待串行用户，每个用户可以使用A/B/C三种不同的调度策略

不同的策略会消耗不同的系统资源

请你根据如下规则进行用户调度

并返回总的消耗资源数

规则是：相邻的用户不能使用相同的调度策略

例如：第一个用户使用A策略 则第二个用户只能使用B和C策略

对单的用户而言，不同的调度策略对系统资源的消耗可以规划后抽象为数值

例如 ：某用户分别使用ABC策略的系统消耗，分别为15 8 17

每个用户依次选择当前所能选择的对系统资源消耗最少的策略,局部最优 如果有多个满足要求的策略，选最后一个

输入描述

第一行表示用户个数N

接下来表示每一行表示一个用户分别使用三个策略的资源消耗 resA resB resC

输出描述：

最优策略组合下的总的系统消耗资源数

样例

示例一：
输入：
3
15 8 17
12 20 9
11 7 5
输出：
24
说明:
1号用户使用B策略
2号用户使用C策略
3号用户使用B策略
系统资源消耗8+9+7
1
2
3
4
5
6
7
8
9
10
11
12
13

C++代码

//
// Created by HANWENKE on 2022/9/3.
//
#include 
#include 
#include 
using  namespace  std;
/*贪心法-局部最优，达到全局最优*/
int main(){
    int n;
    vector<map<int,int > >arr;
    cin>>n;
    arr.reserve(n);
    map<int,int>ismap;
    int x=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>x;
            //记录每个元素的A B C 策略--并已经排好序
            ismap[x]=j;
        }
        arr.push_back(ismap);
        ismap.clear();
    }
    //上一个取的策略
    map<int ,int >ss=arr[0];
    //map的访问--需要使用迭代器--所以这里需要重新定义一个map再使用map的迭代器
    int type=ss.begin()->second;
    //当前策略的值
    int sum=ss.begin()->first;
    if(arr.size()>1){
        //第一个已经取过了，所以下标从1开始
        for(int i=1;i<arr.size();i++){
            ss=arr[i];
            //当前策略值
            int resN=ss.begin()->first;
            //当前的策略类型
            int typeN=ss.begin()->second;
            //当前策略类型和上一个不可以相同
            if(typeN!=type){
                sum+=resN;
                type=typeN;
            }else{
                auto it=ss.begin();
                //先要堆it++不然还是+第一个的值
                sum+=(++it)->first;
                type=it->second;
            }
        }
    }
    cout<<sum;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

合并数组

题目描述：

现在有多组整数数组
需要将他们合并成一个新的数组
合并规则从每个数组里按顺序取出固定长度的内容
合并到新的数组
取完的内容会删除掉
如果该行不足固定长度，或者已经为空
则直接取出剩余部分的内容放到新的数组中继续下一行

输入描述

​ 第一 行每次读取的固定长度
​ 长度0 ​ 第二行是整数数组的数目
​ 数目 0 ​ 第3~n行是需要合并的数组
​ 不同的数组用换行分割
​ 元素之间用逗号分割
​ 最大不超过100个元素

输出描述

输出一个新的数组，用逗号分割

样例：

示例1
    输入
    3
    2
    2,5,6,7,9,5,7
    1,7,4,3,4
    输出
    2,5,6,1,7,4,7,9,5,3,4,7

    说明  获得长度3和数组数目2
    先遍历第一行 获得2,5,6
    再遍历第二行 获得1,7,4
    再循环回到第一行获得7,9,5
    再遍历第二行获得3,4
    再回到第一行获得7

    示例2
    输入
    4
    3
    1,2,3,4,5,6
    1,2,3
    1,2,3,4
    输出
    1,2,3,4,1,2,3,1,2,3,4,5,6
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

C++代码

//
// Created by HANWENKE on 2022/9/3.
//
#include 
#include 
#include 
using namespace std;
int main(){
    //每次要取的数组长度
    int n;
    cin>>n;
    //有几个数组
    int x;
    cin>>x;
    vector<int>temp;
    vector<vector<int > >arr;
    //sum计算总共输入了多少个元素
    int sum=0;
    for(int i=0;i<x;i++){
        int t;
        while(1){
            cin>>t;
            temp.push_back(t);
            sum++;
            if(getchar()=='\n')break;
        }
        arr.push_back(temp);
        temp.clear();
    }
    //结果数组
    vector<int>res;
    //每放一个元素sum--
    while(sum) {
        for (auto &x: arr) {
            //获取嵌套的vector--如果size==0的时候已经不可以取了--直接跳出循环
            if (x.size() == 0)continue;
            int temp = x.size();
            //获取当前的vector中元素的个数和要合并的个数进行比较-如果temp大,那就取n个，如果小与n 不够的时候，取temp个
            int times = min(temp, n);
            //这个循环控制取多少次
            for (int i = 0; i < times; i++) {
                //将第一元素放入到res中--因为每次都删除第一个，所以下次push的时候-依旧是第一个
                res.push_back(x[0]);
                //删除第一个元素，并且计数器--
                x.erase(x.begin());
                sum--;
            }
        }
    }
    //最有以字符串的形式输出
    string s;
    for(auto &x:res){
        //要将数组转化为字符串形式
        s+= to_string(x);
        s+=',';
    }
    //最后多加了一个,所以要去掉
    s.pop_back();
    cout<<s;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62