【习题】N钱买N鸡 O(n)

2024-07-12 21:11| 来源: 网络整理| 查看: 265

N钱买N鸡 Question:LuoGu U124192 N钱买N鸡 Question Link:luogu.com.cn/problem/U124192 Question Algorithm:MathKnowledge Question Difficulty Level:★★☆☆☆ Question Time Complexity:O(n) Question Description: 题目描述

一只公鸡值 5 5 5元，一只母鸡值 3 3 3元，而 1 1 1元可买 3 3 3只小鸡。现有 n n n元钱，想买 n n n只鸡。问有多少种买法？

所有钱要用完,某种鸡可以不买。

输入格式

输入一个数 n n n

输出格式

可行的买法数。

实例输入 100 实例输出 4 数据规模

对于 20 % 20\% 20%的数据：（ 1 ≤ n ≤ 1 0 3 1 ≤ n ≤ 10^3 1≤n≤103）

对于 50 % 50\% 50%的数据：（ 1 ≤ n ≤ 1 0 6 1 ≤ n ≤ 10^6 1≤n≤106）

对于 100 % 100\% 100%的数据：（ 1 ≤ n ≤ 1 0 9 1 ≤ n ≤ 10^9 1≤n≤109）

Question Analysis:

通过数据规模可知，我们至少应该采用 O ( n ) O(n) O(n)以下时间复杂度的算法。首先，我们令 i 为公鸡的数目 j 为母鸡的数目 k 为小鸡的数目 i为公鸡的数目 \quad j为母鸡的数目 \quad k为小鸡的数目 i为公鸡的数目j为母鸡的数目k为小鸡的数目我们枚举小鸡的数目，这样防止发生小鸡的数目不为可被三整除的情况现在，我们有 4 4 4个变量 i , j , k , n i , j , k , n i,j,k,n 据题意，可以得到两个方程 i + j + k = n i+j+k=n i+j+k=n 5 × i + 3 × j + k ÷ 3 × 1 = n 5×i+3×j+k÷3×1=n 5×i+3×j+k÷3×1=n 据上述两方程可解 i = 4 k 3 − n i=\frac{4k}{3}-n i=34k−n j = 2 n − 7 k 3 j=2n- \frac{7k}{3} j=2n−37k

Code:

C++:

#include using namespace std; int n,res=0; int main() { cin >> n; int i,j,k;//i:公鸡的数目 j:母鸡的数目 k:小鸡的数目 //枚举小鸡的数目 for(k=0;k=0&&j>=0) //注意,i,j可能为负，所以需要特判 res++; } cout

【本文地址】

【习题】N钱买N鸡 O(n)

【习题】N钱买N鸡 O(n)

今日新闻

推荐新闻