题目链接
solution
通过拆解公式,可以得出当a[i] < x
时候,进行公式变换后也还是原来的数值,所以我们只用处理大于等于的情况。首先想到的方法是搜索。
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
ll ans = 1e18, x, n, a[30];
vector<int> v;
void dfs(ll last, ll x)
{
if (last >= v.size() || (last < v.size() && x > v[v.size() - 1])) {
ans = min(x, ans);
return;
}
for (int i = last; i < v.size(); i++) {
if (v[i] >= x) {
dfs(i + 1, x + (v[i] / x) * (v[i] + v[i] % x));
}
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> x;
for (int i = 1; i <= n; i++) {
if (a[i] >= x) {
v.emplace_back(a[i]);
}
}
sort(v.begin(), v.end());
dfs(0, x);
cout << ans << endl;
}
int main(){
// IOS;
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}