• 欢迎光临~

# 找零

## 思路

（你说 (1,2,3,4) 四种也行）

## 代码

``````#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;

const ll N = 1e5 + 100;
const ll B = 3000;
ll n, X, f[N * 5];
pair <ll, ll> g[N];
vector <ll> A[5];
ll may[5];

//x.first/x.second<y.first/y.second
bool cmp(pair <ll, ll> x, pair <ll, ll> y) {
return x.first * y.second < y.first * x.second;
}

int main() {
scanf("%lld %lld", &n, &X);
for (ll i = 1; i <= n; i++) {
ll a; scanf("%lld", &a);
ll x = (a + 4) / 5; ll y = x * 5 - a;
g[i] = make_pair(x, y);
A[y].push_back(x);
}
for (ll i = 0; i < 5; i++) sort(A[i].begin(), A[i].end());

sort(g + 1, g + n + 1, cmp);
ll num = X / 5;
for (ll i = 1; i <= n; i++) {
if (num < g[i].first) break;
num -= g[i].first; may[g[i].second]++;
}
num = X / 5; ll an = X % 5, sum = 0;
memset(f, 0x7f, sizeof(f)); f[0] = 0;
for (ll sz = 0; sz < 5; sz++) {
ll l = max(1ll, may[sz] - B), r = min((ll)A[sz].size(), may[sz] + B);
for (ll i = 1; i < l; i++) {
an += sz; num -= A[sz][i - 1];
}
for (ll i = l; i <= r; i++) {
for (ll j = sum; j >= 0; j--) {
f[j + sz] = min(f[j + sz], f[j] + A[sz][i - 1]);
}
sum += sz;
}
}

for (ll i = sum; i >= 0; i--)
if (f[i] <= num) {
an += i; break;
}
printf("%lld", an);

return 0;
}
``````