算法-全排列

1、全排列函数的使用

举例：{1,2,3}的全排列

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){ll a[3] = {1, 2, 3};do{for (ll i = 0; i < 3;i++){cout << a[i] << " ";}cout << endl;} while (next_permutation(a, a + 3));
}

2、算法题应用

B-小苯购物_牛客周赛 Round 94

题目描述： 给我们3个优惠券，每个优惠券存在两个参数a，b。表示只有商品价格大于a元的时候我们才可以优惠b元。每种商品我们可以选或者不选。给出一开始商品的价格n，问最终n的最小值为多少？

本题思路：

1. b都是大于0的，如果可以选择优惠我们选就比不选好。
2. 但是这样就会存在一些问题，选择优惠之后可能商品的价格会变低，影响后面商品优惠的选择，说明这个又和优惠券的选择顺序有关。
3. 本题只存在3个优惠券，我们枚举出所有选择的全排列进行依次比较即可，这样以来我们就可以考虑到所有的选择情况了。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n; // 商品初始价格
ll a[3], b[3]; // 三个优惠券的参数，a[i]表示优惠阈值，b[i]表示优惠金额
// 函数f，用于计算在特定优惠券选择顺序下的最终价格
ll f(ll i, ll j, ll k) {ll m = n; // 初始化当前价格为初始价格n// 检查第一个优惠券是否可用，如果可用则应用优惠if (a[i] <= m) m -= b[i];// 检查第二个优惠券是否可用，如果可用则应用优惠if (a[j] <= m) m -= b[j];// 检查第三个优惠券是否可用，如果可用则应用优惠if (a[k] <= m) m -= b[k];// 如果最终价格小于0，则设置为0if (m < 0) m = 0;return m; // 返回最终价格
}
void solve() {cin >> n; // 读取商品初始价格n// 读取三个优惠券的参数for (ll i = 0; i < 3; i++) {cin >> a[i] >> b[i];}ll mx = n; // 初始化最小价格为初始价格nll c[3] = {0, 1, 2}; // 优惠券选择顺序的初始排列// 遍历所有可能的优惠券选择顺序do {ll v = f(c[0], c[1], c[2]); // 计算当前顺序下的最终价格// 如果当前最终价格小于当前最小价格，则更新最小价格if (v < mx) {mx = v;}} while (next_permutation(c, c + 3)); // 生成下一个排列cout << mx << endl; // 输出最小价格
}
int main() {ll t;cin >> t;while (t--) { solve(); }
}