题目链接:点击打开链接
题意:
给定n种面额,每次ATM机能吐k张纸钞。(且每次ATM机只能吐至多2种面额)
q个询问,每次回答若一次能吐出该面额的最少纸张数量,若不能则输出-1
O(n*k*k*logn)能过
#include<iostream> #include<stdio.h> #include<string.h> #include <algorithm> #include<string> #include<set> #include<vector> #include<queue> #include<math.h> template <class T> inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } using namespace std; typedef long long ll; const int N = 5005; const int inf = 1000000; int n, k; ll a[N]; int hehe; int dd; set<ll>myset; ll work(ll x){ ll ans = inf; for (int i = 1; i <= n; i++){ if (x%a[i] == 0 && x / a[i] <= k) ans = min(ans, x / a[i]); for (int j = 0; j <= k; j++){ ll y = x - a[i] * j; for (int z = 1; z <= k; z++){ if (z + j > k)break; if (y%z == 0 && myset.count(y / z)) ans = min(ans, (ll)z + j); } } } if (ans == inf)return -1; return ans; } int main(){ while (cin >> n >> k){ myset.clear(); for (int i = 1; i <= n; i++)rd(a[i]), myset.insert(a[i]); int q; rd(q); while (q--){ ll x; rd(x); pt(work(x)); puts(""); } } return 0; }
Codeforces 529E The Art of Dealing with ATM 简单题
原文:http://blog.csdn.net/qq574857122/article/details/44536957