思路：
1、暴力枚举每种面值的张数，将可以花光的钱记录下来。每次判断n是否能够用光，能则输出0，不能则向更少金额寻找是否有能够花光的。时间复杂度O(n)
2、350 = 200 + 150，买350的道具可用一个150和200的代替，那么直接考虑200和150的道具即可。首先全部买150的道具，剩下的金额为x，可以看成t = x / 50张50的钱加上r = x % 50的钱。如果t <= n / 150，那么说明这些50的都可以和一个150的买200的道具，否则会剩下一些50的没法用。假设最后剩余k张50，那么小费就是50 * k + t. 时间复杂度O(1)
第一种方法AC代码：
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000")#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int>typedef long long LL;const int maxn = 10000 + 5;int a[maxn];int u[] = {150, 200, 350};void init() {memset(a, 0, sizeof(a));for(int i = 0; i < 70; ++i)for(int j = 0; j < 55; ++j)for(int k = 0; k < 30; ++k) {int sum = i * 150 + j * 200 + k * 350;if(sum > 10000) continue;else a[sum] = 1;}}int find(int n) {if(a[n]) return 0;//leftint ans = n;for(int i = n-1; i >= 0; --i) {if(a[i]) {ans = n - i;break;}}return ans;}int main() {init();int n, T;scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d\n", find(n));}return 0;}
第二种方法AC代码：
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000")#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int>typedef long long LL;const int maxn = 1e4 + 5;int main() {int T, n;scanf("%d", &T);while(T--) {scanf("%d", &n);int u = n % 150, v = n / 150;if(u == 0) printf("0\n");else {int k = u / 50, h = u % 50;printf("%d\n", h + 50 * (k - min(v, k)));}}return 0;}
如有不当之处欢迎指出！
