买不到的数目

阳光穿透心脏的1/2处 2024-03-30 16:07 66阅读 0赞

## 买不到的数目 ##

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式  
两个正整数 n,m，表示每种包装中糖的颗数。

输出格式  
一个正整数，表示最大不能买到的糖数。

数据范围  
2≤n,m≤1000，  
保证数据一定有解。

输入样例：  
4 7  
输出样例：  
17

**算法思路**：  
先开一个`bool`类型`dp`数组，`dp[i]`表示能否组成`i`。  
两个数据分别是`n`,`m`，假定最小值是`minn`，最大值是`maxx`，那么就相当于从`minn`开始，不断往前走，每走到一个数，都要看看`dp[i - n]`或者`dp[i - m]`是否为`true`，如果是，则置`true`，反之我们需要更新`ans`，`ans`就是指最大不能买的数目，也就是我们最后的输出，循环结束，便可直接输出`ans`.

**特解答案**：

#include<iostream>
    using namespace std;
    int main()
    {
        
        int a, b;
        cin >> a >> b;
        cout << a * b - a - b;
        return 0;
    }

正常解C++

#include <iostream>
    #include <algorithm>
    using namespace std;
    int n, m, minn, maxx, ans;
    bool dp[1000000];
    int main() {
        
        cin >> n >> m;
        dp[0] = true;
        minn = min(n, m);
        maxx = max(n, m);
        for (int i = minn; i < n * m; i++) {
        
            if (dp[i - minn]) {
        
                dp[i] = true;
            } else if (i >= maxx && dp[i - maxx]) {
        
                dp[i] = true;
            } else {
        
                ans = i;
            }
        }
        cout << ans;
        return 0;
    }

正常解Java

import java.util.*;
    
    
    public class Main
    {
        		
    	static int N = 1000010;
    	static boolean [] f = new boolean [N];
    	public static void main(String[] args) {
        
    		Scanner in = new Scanner (System.in);
    		int n = in.nextInt();
    		int m = in.nextInt();
    		int mi = Math.min(n, m);
    		int ma = Math.max(n, m);
    		int res = 0;
    		f[0] = true;
    		for (int i = mi; i <= n * m; ++ i)
    		{
        
    			if (f[i - mi]) f[i] = true;
    			else if (i >= ma && f[i - ma]) f[i] = true;
    			else res = i;
    		}
    		System.out.println(res);
    	}
    }