HDU - 1248 寒冰王座数学or暴力枚举

小灰灰 2021-01-08 14:08 456阅读 0赞

思路：

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;
    	//left
    	int 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代码：