买苹果_牛客题霸_牛客网

描述

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

输入描述：

输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述：

输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

示例1

输入：

20

复制

输出：

3

复制

贪心暴力

贪心算法暴力求解,首先计算出选择8袋子的最大可以选择的数量,然后计算次数的情况是否可以正好装好n个苹果.

如果不行,8袋子数量减少1,然后继续计算,直到第一次遇到的可以的选择,次数就是最优的解.

#include <iostream> // 包含标准输入输出库
using namespace std; // 使用标准命名空间std

int main() { // 程序的主函数
    int n; // 声明一个整型变量n，用来存储需要购买的苹果的数量
    cin >> n; // 从标准输入读取苹果的数量n
    int bag8 = n >> 3; // 使用位运算右移3位来计算可以最大使用多少个8个一袋的包装，等同于n除以8的整数部分
    int rest; // 声明一个整型变量rest，用来存储除去最大可能的8个每袋后剩余的苹果数
    while (bag8 >= 0) { // 当8个每袋的包装数大于或等于0时循环
        rest = n - bag8 * 8; // 计算去掉8个每袋苹果后剩余的苹果数
        if (rest % 6 == 0) { // 如果剩余的苹果数能被6整除
            cout << bag8 + (rest / 6); // 输出使用的总袋数（8个每袋的袋数加上6个每袋的袋数）
            return 0; // 程序结束，返回0
        }
        bag8--; // 如果不能被6整除，则减少一个8个每袋的袋数，再次尝试
    }
    cout << -1; // 如果所有可能都尝试过后仍然不能正好买到n个苹果，输出-1
}

打表找规律

如果时间复杂度要求很大,可以通过暴力解的方式去求解小部分的答案,将小部分的答案全部列出来寻找数学规律.

有的题目有规律有的题目没有规律,纯属算作是一个技巧.

#include <iostream>
using namespace std;

void f(int n) {
    int bag8 = n >> 3;
    int rest;
    while (bag8 >= 0) {
        rest = n - bag8 * 8;
        if (rest % 6 == 0) {
            cout << bag8 + (rest / 6)<<endl;
            return  ;
        }
        bag8--;
    }
    cout << -1<<endl;
}
int main() {
    for(int i=1;i<=200;i++){
        cout<<i<<":";
        f(i);
    }

}

#include <iostream> // 包含标准输入输出库
using namespace std; // 使用标准命名空间std

int main() { // 主函数
    int n; // 声明一个整型变量n，用来存储需要购买的苹果的数量
    cin >> n; // 从标准输入读取苹果的数量n

    // 计算从18个苹果开始，每增加8个苹果，袋数增加一个的目标袋数
    int aim = (n - 18) / 8 + 3; 

    if (n < 18) { // 如果需要的苹果数少于18个
        if (n == 6 || n == 8) { // 如果恰好是6个或8个
            cout << 1; // 输出需要1袋
            return 0; // 程序结束
        } else if (n == 12 || n == 14 || n == 16) { // 如果是12个，14个或16个
            cout << 2; // 输出需要2袋
            return 0; // 程序结束
        } else { // 如果不是上述的任何一个数
            cout << -1; // 输出-1，表示无法恰好组成
            return 0; // 程序结束
        }
    }

    // 如果n大于等于18且n-18后是偶数
    if (((n % 8) & 1) == 0) { // 判断n除以8的余数是否为偶数
        cout << aim; // 输出计算得到的袋数
        return 0; // 程序结束
    }
    cout << -1; // 如果上面的条件不成立，输出-1，表示无法恰好组成
}

牛牛爱博弈

链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

牛牛和牛妹玩博弈游戏。

牛牛：我们来玩取石子游戏。一共有n堆石子，每个人每次可以取1或2颗石子，谁取走了最后一颗石子就算谁获胜。

牛妹：这游戏太无聊了。

牛牛：那改一改。一共有n堆石子，每个人每次可以取1,2,4,8,...2k2^k2k颗石子，谁取走了最后一颗石子就算谁获胜。

牛妹：好的，你先开始取吧。

牛牛心里知道自己是否有必胜策略，但他想来考考你。

因为牛牛和牛妹很爱玩这种游戏，所以本题有多组数据。

（注：牛牛叫Alan\color{grey}{Alan}Alan，牛妹叫Frame\color{black}{F}\color{red}{rame}Frame.）

输入描述:

第一行，输入数据组数T。

接下来T行，每行一个数n。

输出描述:

对于每一组数据，

如果牛牛必胜，则输出“Alan”（不含引号）；

如果牛妹胜，则输出“Frame”（不含引号）。

（PS:牛牛叫 Alan ，牛妹叫 Frame ）

示例1

输入

复制3 1 2 3

3

1

2

3

输出

复制Alan Alan Frame

Alan

Alan

Frame

说明

当n=1时，牛牛直接取1颗石子即可获胜。

当n=2时，牛牛直接取2颗石子即可获胜。

当n=3时，显然牛牛论怎么取，牛妹都可以获胜。

示例2

输入

复制3 17 18 19

3

17

18

19

输出

复制Alan Frame Alan

Alan

Frame

Alan

备注:

数据保证1≤T≤1000,1≤n≤2×1091\le T\le 1000,1\le n\le 2\times 10^91≤T≤1000,1≤n≤2×109

1.

移动方式是2^k次方,对3取余==0 <==> 后者赢.

移动方式是3^k次方或者4^k次方等等,都不能利用取余的方式解决问题.而是需要递归或者动态规划求解问题.

2.

把解决方法用函数solve封装起来.利用函数封装黑盒让代码看起来清晰.

3.

在很多博弈论问题中，找到周期性或模式（例如模3）是常见的策略，尽管这里没有深入解释这一点的具体数学逻辑，这种模式通常是通过详细的博弈分析获得的。

周期性指的是找规律,使用打表法即可.

#include<bits/stdc++.h> // 包含几乎所有的C++标准库
using namespace std; // 使用标准命名空间std
using ll=long long; // 定义别名ll为long long类型，用于处理大整数

void solve(){ // 定义solve函数，用于解决每个测试案例
    int n; // 声明整型变量n，用于存储每个案例的石子数量
    cin >> n; // 从标准输入读取石子的数量
    if(n % 3 == 0) cout << "Frame" << endl; // 如果n除以3的余数为0，输出"Frame"
    else cout << "Alan" << endl; // 否则输出"Alan"
}

int main(){ // 主函数
    int t; // 声明整型变量t，用于存储测试案例的数量
    cin >> t; // 从标准输入读取测试案例的数量
    for(int i = 1; i <= t; i++){ // 循环从1到t，对每个测试案例调用solve函数
        solve(); // 调用solve函数处理每个测试案例
    }
}

829. 连续整数求和

给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。

示例 1:

输入: n = 5 输出: 2 解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

示例 2:

输入: n = 9 输出: 3 解释: 9 = 4 + 5 = 2 + 3 + 4

示例 3:

输入: n = 15 输出: 4 解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示:

• 1 <= n <= 10(9)

1.

取余的性质整除性,A%k==0 <==>存在一个B满足A=k*B.

2.

将 n 表示成 k 个连续的正整数之和。

设第一个数为x，连续的k个数之和为x+(x+1)+ ... + (x+k-1) = k * x + (1+2+...+k-1) = k * x + k(k-1)/2。

能表示的条件为n=k * x + k(k-1)/2 (x≥1,k≥1), 令k(k-1)/2=sum,得到n-sum=k*x,如果x存在,等价于(n-sum)%k==0,即 (n−sum) mod k = 0。

3.

首先k表示的是连续序列个数,对于每一个k只有两种情况,要么存在x要么不存在x.

class Solution { // 定义一个解决方案类
public:
    int consecutiveNumbersSum(long long n) { // 成员函数，用来计算连续数之和为n的组数
        int sum = 0; // 初始化sum，用来计算当前考虑的连续整数之和
        int ans = 0; // 初始化ans，用来计数满足条件的连续整数组数
        
        for (int i = 1; ; i++) { // 用i来表示连续数字的长度，从1开始无限循环
            sum += i - 1; // 在每次循环开始，将上一次的i-1加到sum上，这实际上是一个计算从1到i-1的部分和
            if (n - sum <= 0) break; // 如果n减去当前的sum小于等于0，则终止循环
            if ((n - sum) % i == 0) ans++; // 如果n减去sum后可以整除i，则说明存在一组长度为i的连续正整数其和为n
        }
        return ans; // 返回满足条件的组数
    }
};

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！