题面描述

在通信系统中，一个常见的问题是对用户进行不同策略的调度，会得到不同的系统消耗和性能。

假设当前有 $n$ 个待串行调度用户，每个用户可以使用 $A/B/C$ 三种不同的调度策略，不同的策略会消耗不同的系统资源。

请你根据如下规则进行用户调度，并返回总的消耗资源数。

规则：

1. 相邻的用户不能使用相同的调度策略，例如，第 $1$ 个用户使用了 $A$ 策略，则第 $2$ 个用户只能使用 $B$ 或者 $C$ 策略。
2. 对单个用户而言，不同的调度策略对系统资源的消耗可以归一化后抽象为数值。
3. 每个用户依次选择当前所能选择的对系统资源消耗最少的策略（局部最优），如果有多个满足要求的策略，选最后一个。

思路

贪心。

策略选择：

• 对于第一个用户，直接选择消耗最小且在有多个最小值时选择最后一个策略。
• 对于后续用户，排除与前一个用户相同的策略，从剩下的两个策略中选择消耗最小的策略，如果有多个最小值，选择最后一个。

贪心证明

要证明这个贪心策略的正确性，我们可以分为两个部分进行论证：第一个用户的策略选择和后续用户的策略选择。

1. 第一个用户的策略选择

对于第一个用户，我们直接选择其三种策略中消耗最小的策略。如果有多个策略具有相同的最小消耗，我们选择最后一个策略。由于没有前一个用户的限制，选择消耗最小的策略自然是合适的。此时的选择不会影响后续用户的选择，因为没有策略的限制。

2. 后续用户的策略选择

对于每个后续用户，我们需要确保所选策略与前一个用户不同。我们只考虑与前一个用户策略不同的两种选择。根据贪心选择的原则，在这两种选择中选择消耗最小的策略，如果存在多个相同的最小消耗值，则选择最后一个策略。

我们可以通过反证法来证明这个选择是正确的：

假设在第 $i$ 个用户的选择中，选择了策略 $X$ 而非最优策略 $Y$（即 $Y$ 是在排除与前一个用户策略相同的情况下的最佳选择）。根据贪心策略的选择原则，$Y$ 的消耗必然小于 $X$，并且因为我们排除了前一个用户的策略，$Y$ 是合法的。

这会导致以下矛盾：

• 如果选择 $X$，则总消耗会增加，而我们的目标是最小化总消耗。
• 因此，选择 $Y$ 必然会得到更优的消耗。

由此可见，后续用户的贪心选择确保了每一步都是在当前约束条件下的局部最优，而不影响全局最优的达成。因此，通过逐步选择使得系统资源消耗最小的策略，最终的总消耗是最优的。

综上所述，这个贪心策略在每一步的选择都是合理且最优的，从而证明了其正确性。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    // 存储每个用户的三个策略消耗
    vector<vector<int>> users(n, vector<int>(3));
    for(int i=0;i<n;i++){
        cin >> users[i][0] >> users[i][1] >> users[i][2];
    }
    int total = 0;
    // 记录前一个用户选择的策略，0表示未选择
    int prev_strategy = -1;
    for(int i=0;i<n;i++){
        // 找当前用户可选的最小消耗策略
        int min_cost = INT32_MAX;
        int chosen_strategy = -1;
        for(int s=0;s<3;s++){
            // 排除与前一个用户相同的策略
            if(s != prev_strategy){
                if(users[i][s] < min_cost){
                    min_cost = users[i][s];
                    chosen_strategy = s;
                }
                else if(users[i][s] == min_cost){
                    // 选择最后一个
                    if(s > chosen_strategy){
                        chosen_strategy = s;
                    }
                }
            }
        }
        // 累加消耗
        total += min_cost;
        // 更新前一个策略
        prev_strategy = chosen_strategy;
    }
    cout << total;
    return 0;
}

python

# 读取用户数量
n = int(input())
# 存储每个用户的三个策略消耗
users = []
for _ in range(n):
    res = list(map(int, input().split()))
    users.append(res)

total = 0
prev_strategy = -1  # 前一个用户选择的策略，-1表示未选择

for i in range(n):
    min_cost = float('inf')
    chosen_strategy = -1
    for s in range(3):
        if s != prev_strategy:
            if users[i][s] < min_cost:
                min_cost = users[i][s]
                chosen_strategy = s
            elif users[i][s] == min_cost:
                if s > chosen_strategy:
                    chosen_strategy = s
    total += min_cost
    prev_strategy = chosen_strategy

print(total)

java

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 存储每个用户的三个策略消耗
        int[][] users = new int[n][3];
        for(int i=0;i<n;i++){
            users[i][0] = sc.nextInt();
            users[i][1] = sc.nextInt();
            users[i][2] = sc.nextInt();
        }
        int total = 0;
        int prev_strategy = -1; // 前一个用户选择的策略，-1表示未选择
        for(int i=0;i<n;i++){
            int min_cost = Integer.MAX_VALUE;
            int chosen_strategy = -1;
            for(int s=0;s<3;s++){
                if(s != prev_strategy){
                    if(users[i][s] < min_cost){
                        min_cost = users[i][s];
                        chosen_strategy = s;
                    }
                    else if(users[i][s] == min_cost){
                        if(s > chosen_strategy){
                            chosen_strategy = s;
                        }
                    }
                }
            }
            total += min_cost;
            prev_strategy = chosen_strategy;
        }
        System.out.println(total);
    }
}

题目描述

在通信系统中，一个常见的问题是对用户进行不同策略的调度，会得到不同的系统消耗和性能。

假设当前有 $n$ 个待串行调度用户，每个用户可以使用 $A/B/C$ 三种不同的调度策略，不同的策略会消耗不同的系统资源。

请你根据如下规则进行用户调度，并返回总的消耗资源数。

规则：

相邻的用户不能使用相同的调度策略，例如，第 $1$ 个用户使用了 $A$ 策略，则第 $2$ 个用户只能使用 $B$ 或者 $C$ 策略。

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

例如，某用户分别使用 $A/B/C$ 策略的系统消耗分别为 $15/8/17$ 。

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

输入描述

第一行表示用户个数 $n$

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

输出描述

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

样例1

输入

3
15 8 17
12 20 9
11 7 5

输出

24

说明

$1$ 号用户使用 $B$ 策略，$2$ 号用户使用 $C$ 策略，$3$ 号用户使用 $B$ 策略。

系统资源消耗: $8 + 9 + 7 = 24$ 。