今天 2024 秋令营 Day1 的 贪心 例题,来解释一下这道题贪心的思路。
首先输入一个整数 \(n\),表示需要处理的数字数量为 \(2^n - 1\),随后输入每个编号的代价,并将代价和编号存储在数组 \(a\) 中。接着,对代价进行排序,以便在后续处理中优先选择代价较小的数字。然后,使用一个 \(vis\) 数组来标记哪些编号已经被选择,对于每个未选择的编号,选择它并将其代价加入总代价中,同时通过异或操作更新 \(vis\) 数组,以标记出可以由当前选择的编号生成的所有编号。最后,程序输出计算得到的最小代价。
最后上一下代码。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn= 1e5+10;
int vis[maxn], n; // vis数组用于记录已选择的编号,n是输入的数字数量
ll ans; // 用于存储最终的最小代价
pair<int,int> a[maxn]; // 数组a存储每个数字的代价和对应的编号
int main() {
scanf("%d", &n); // 输入n,表示2的n次方
n = 1 << n; // 计算2^n的值
for (int i = 1; i < n; i++) {
scanf("%d", &a[i].first); // 输入代价,存入a数组的first部分
a[i].second = i; // 将编号存入a数组的second部分
}
sort(a + 1, a + n); // 按照代价排序,从小到大
vis[0] = 1; // 初始化vis数组,标记编号0已被选择
for (int i = 1; i < n; i++) { // 遍历每个数字
if (vis[a[i].second]) continue; // 如果该编号已被选择,跳过
ans += a[i].first; // 将当前代价加到总代价中
for (int j = 0; j < n; j++) { // 更新vis数组
if (vis[j]) // 如果j编号已被选择
vis[j ^ a[i].second] = 1; // 将j与当前编号的异或结果标记为已选择
}
}
printf("%lld\n", ans); // 输出最终的最小代价
return 0;
}
标签:int,题解,ABC236F,vis,maxn,数组,编号,Spices,代价
From: https://www.cnblogs.com/zenoszheng/p/18612304