1 条题解

  • 0
    @ 2026-2-1 15:46:23
    #include <bits/stdc++.h>
    using namespace std;
    
    // 存储每个位置的原始值s、目标值t和变换代价系数c
    struct node{
        int s,t,c;
    }arr[1000100];
    
    // 比较函数:按变换代价系数c从小到大排序,用于贪心策略
    bool cmp(node x,node y){
        return x.c < y.c; 
    }
    
    int main(){
        int n;
        cin >> n; // [1] 输入序列长度n
        int a = n; // [2] a初始为总长度,后续统计不匹配的位置数量
        
        // [3] 输入原始序列S,存入每个位置的s值
        for(int i = 0; i < n; i++) 
            cin >> arr[i].s;
        
        // [4] 输入目标序列T,存入每个位置的t值,并统计初始不匹配的位置数量a
        for(int i = 0; i < n; i++){
            cin >> arr[i].t;
            if(arr[i].s == arr[i].t) 
                a--; // 位置s和t相同,无需变换,不匹配数减1
        }
        
        // [5] 输入每个位置的变换代价系数c
        for(int i = 0; i < n; i++) 
            cin >> arr[i].c; 
        
        // [6] 按代价系数c从小到大排序,优先处理代价小的位置
        sort(arr, arr + n, cmp);
        
        long long sum = 0; // 存储最小总代价,用long long避免溢出
        // [7] 遍历所有位置,计算总代价
        for(int i = 0; i < n; i++){
            // 仅处理需要变换的位置(s≠t)
            if(arr[i].s != arr[i].t){
                sum += arr[i].c * a; // 当前代价=系数c × 当前不匹配数a
                a--; // 处理完一个不匹配位置,剩余不匹配数减1
            }
        }
        
        cout << sum; // [8] 输出最小总代价
        return 0;
    }
    
    • 1

    信息

    ID
    1032
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    2
    已通过
    1
    上传者