1 条题解
-
0
#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
- 上传者