贪心算法 + 指针移动
2026-06-06 14:36:49
发布于：湖北
35阅读
0回复
0点赞
题目背景
- 有
n种武器，m个材料 - 每个材料原本适配某个武器，可以花费一定代价修改为适配其他武器
- 目标：让适配武器1的材料数量 严格大于 其他所有武器
- 求解：最小总花费
#include <bits/stdc++.h>
using namespace std;
vector<long long> a[100000];
int cnt[100000], idx[100000];
int main(){
int n, m;
cin >> n >> m;
//循环输入存储
for(int i = 0; i < m; i++) {
long long x1, x2;
cin >> x1 >> x2;
a[x1].push_back(x2);
cnt[x1]++;
}
//排序
for(int i = 1; i <= n; i++)sort(a[i].begin(),a[i].end());
//特判
long long res = 0;
while(true){
//大值
int mx = 0;
for(int i = 2; i <= n; i++) mx = max(mx,cnt[i]);
if(cnt[1] > mx) break;
//小值
long long mn = 1e18;
int pos = -1;
for(int i = 2; i <= n; i++) {
if(idx[i] < a[i].size() &&a[i][idx[i] ] < mn) {
mn = a[i][idx[i] ];
pos = i;
}
}
if(pos == -1){
res = -1;
break;
}
res += mn;
cnt[pos]--;
cnt[1]++;
idx[pos]++;
}
cout << res << endl;
return 0;
}
代码逐段解析
1. 数据结构定义
vector<long long> a[100000]; // a[i]: 存储原本适配武器i的材料的花费列表
int cnt[100000], // cnt[i]: 当前适配武器i的材料数量
idx[100000]; // idx[i]: 武器i的材料已处理到的位置（贪心指针）
| 变量 | 含义 | 作用 |
|---|---|---|
a[i] |
武器 i 的材料花费数组 | 排序后贪心选最小花费 |
cnt[i] |
武器 i 的当前材料数 | 判断是否满足条件 |
idx[i] |
武器 i 的贪心指针 | 避免重复选择同一材料 |
2. 输入与预处理
for(int i = 0; i < m; i++) {
long long x1, x2;
cin >> x1 >> x2; // x1: 原适配武器, x2: 修改花费
a[x1].push_back(x2); // 存入对应武器的花费列表
cnt[x1]++; // 该武器材料数+1
}
// 对每个武器的材料花费从小到大排序
for(int i = 1; i <= n; i++)
sort(a[i].begin(), a[i].end());
目的：排序后，a[i][0] 就是武器 i 最便宜的可修改材料，方便贪心选择。
3. 主循环：贪心转移
long long res = 0; // 总花费
while(true) {
// 【步骤1】检查是否满足终止条件
int mx = 0;
for(int i = 2; i <= n; i++)
mx = max(mx, cnt[i]); // 找其他武器的最大材料数
if(cnt[1] > mx) break; // 武器1严格大于所有其他 → 成功！
终止条件：cnt[1] > max(cnt[2], cnt[3], ..., cnt[n])
// 【步骤2】找其他武器中"最便宜的可转移材料"
long long mn = 1e18; // 初始化最小花费为无穷大
int pos = -1; // 记录最便宜材料所属的武器编号
for(int i = 2; i <= n; i++) {
// idx[i] < a[i].size() 确保还有未使用的材料
// a[i][idx[i]] 是当前武器最便宜的可用材料
if(idx[i] < a[i].size() && a[i][idx[i]] < mn) {
mn = a[i][idx[i]]; // 更新最小花费
pos = i; // 记录武器编号
}
}
贪心策略：每次选花费最小的材料从其他武器转移到武器1。
// 【步骤3】执行转移 或 判断无解
if(pos == -1) { // 所有其他武器都没材料可转移了
res = -1;
break;
}
// 执行转移操作：
res += mn; // 累加花费
cnt[pos]--; // 原武器材料数-1
cnt[1]++; // 武器1材料数+1
idx[pos]++; // 该武器的贪心指针后移（标记已使用）
}
转移效果：
- 武器1：
+1 - 其他武器
pos：-1 - 一增一减，相对优势
+2，效率最高！
4. 输出结果
cout << res << endl;
return 0;
算法正确性证明
为什么贪心选最小花费是最优的？
核心观察：每次转移操作的效果是固定的：
- 武器1的材料数
+1 - 某个其他武器的材料数
-1 - 总花费 = 该材料的修改代价
贪心选择性质：
- 假设存在最优解，其中某次转移选了花费
c1的材料 - 如果存在更便宜的材料
c2 < c1可选 - 用
c2替换c1，操作效果相同，但总花费更小 - 矛盾！所以最优解必然每次选最小花费
无后效性：
- 每次转移只影响两个武器的计数
- 不影响其他材料的花费
- 局部最优 → 全局最优
复杂度分析
| 步骤 | 时间复杂度 | 说明 |
|---|---|---|
| 输入 + 排序 | 每个材料排序一次 | |
| 主循环 | 最多转移 次，每次遍历 个武器 | |
| 总计 | 时完全可行 |
样例模拟
输入：
3 5
1 10 // 武器1，花费10
2 5 // 武器2，花费5
2 8 // 武器2，花费8
3 3 // 武器3，花费3
3 7 // 武器3，花费7
初始状态：
cnt[1]=1, cnt[2]=2, cnt[3]=2
a[1]=[10], a[2]=[5,8], a[3]=[3,7] (已排序)
idx=[0,0,0,0]
第1轮循环：
- 检查：
cnt[1]=1,mx=max(2,2)=2,1>2?❌ - 找最小：
a[2][0]=5,a[3][0]=3→ 选武器3，花费3 - 转移：
res=3,cnt[3]=1,cnt[1]=2,idx[3]=1
第2轮循环：
- 检查：
cnt[1]=2,mx=max(2,1)=2,2>2?❌（需要严格大于） - 找最小：
a[2][0]=5,a[3][1]=7→ 选武器2，花费5 - 转移：
res=8,cnt[2]=1,cnt[1]=3,idx[2]=1
第3轮循环：
- 检查：
cnt[1]=3,mx=max(1,1)=1,3>1?✅ - 退出循环，输出
8
验证：最终 cnt=[3,1,1]，武器1严格大于其他，总花费 3+5=8 ✓
注意事项
idx数组的作用：避免重复选择同一材料，确保每个材料最多被转移一次pos == -1的判断：处理无解情况（其他武器材料都用完了还不满足条件）long long的使用：花费可能很大，防止溢出- 严格大于：条件是
cnt[1] > mx，不是>=
对于 ，当前 的写法已经足够高效。
总结
- 每次选择花费最小的材料，从其他武器转移到武器1
- 直到武器1的材料数严格大于所有其他武器
- 时间复杂度 ，空间复杂度
有帮助，赞一个