19 条题解

  • 37
    @ 2023-3-26 21:09:59

    P1012 文具采购

    题目描述

    禾木的班上共有 n 元班费，同学们准备使用班费集体购买 3 种物品：

    1. 圆规，每个 7 元。
    2. 笔，每支 4 元。
    3. 笔记本，每本 3 元。

    禾木负责订购文具，设圆规，笔，笔记本的订购数量分别为 a,b,c，他订购的原则依次如下：

    1. n 元钱必须正好用光，即 7a+4b+3c=n。
    2. 在满足以上条件情况下，成套的数量尽可能大，即 a,b,c 中的最小值尽可能大。
    3. 在满足以上条件情况下，物品的总数尽可能大，即 a+b+c 尽可能大。

    请你帮助禾木求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。

    思路

    直接算肯定TLE，这是三层嵌套，10的5次方，100000 * 100000 * 100000 = 1000000000000000，1百万亿，加上简单简化，也不太行。

    这里就不说普通解法了。

    题目要求a，b，c的最小值尽可能大，所以就要让它们的最小值越接近n/14越好。如果a，b，c的最小值为n/14 时无解，则让a,b,c的最小值为n/14−1，以此类推，直到有解为止；

    这样一下数据缩了好多，之后再用普通解法就可以了

        for(int a = n / 14;a >= 0;a--)
    for(int b = a;b <= n / 3;b++)
    for(int c = a;c <= n / 3;c++)

    在加上一个判断：

    if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }

    和成一下。

    参考代码：

    #include <iostream>//hetao3097453
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}

    hetao3097453

    2023年3月26日

  • 13
    @ 2023-2-28 15:27:11
    思路
    Step1:朴素算法
    这道题首先分析，直接枚举a,b,c所有可能性，但n=10^5时，a需要从0枚举到n/7,b需要从0枚举到n/4，再计算c时可能会超时，所以需要合理分析。

    Step2：先满足条件2：
    题目要求a，b，c的最小值尽可能大，所以就要让它们的最小值越接近n/14越好。如果a，b，c的最小值为n/14 时无解，则让a,b,c的最小值为n/14−1，以此类推，直到有解为止；

    Step3:再考虑条件3.a+b+c尽可能大
    举两个例子：
    1.当n=7时，可以分为一个a，或者一个b和一个c。 因为1a=1b+1c，一个a可以被拆成一个b和一个c,所以此时a一定会是三者中的最小值。否则可以将1b和1c合并成1a，此时最小值更小。
    2.当n=12时，可以分为3个b，或者4个c。
    希望和最大，显然b和c中尽可能分出c，剩下得考虑b

    Step4:归纳解法
    所以就有这样的解法：
    a从n/14 开始往下枚举。然后依次枚举c，b，一旦遇到有解就输出，结束程序。此时的解就是最优解。注意枚举范围，b最大为n/4，c最大为n/3。最后如果无解，输出−1。


    Step5:时间复杂度说明
    虽然看上去时间复杂度是O（n^3），但是最终结果实际上只和n除以14的余数有关，所以是O(1).

    代码 
    
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int main()
{
    cin >> n;
    for (int a = n / 14; a >= 0; a--) //枚举最小值，也就是a的个数
    {
        for (int b = a; b <= n / 4; b++) //枚举b
            for (int c = a; c <= n / 3; c++) //枚举c
                if (a * 7 + b * 4 + c * 3 == n) //如果有解
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;//输出，结束程序
                }
    }
    cout << "-1" << endl;//无解,输出-1
    return 0;
}
    • 7
      @ 2023-7-27 16:02:39

      p1012

      -题目回顾-

      禾木的班上共有 n 元班费，同学们准备使用班费集体购买 3 种物品：

      1. 圆规，每个 7 元。
      2. 笔，每支 4 元。
      3. 笔记本，每本 33 元。

      禾木负责订购文具，设圆规，笔，笔记本的订购数量分别为 a,b,c，他订购的原则依次如下：

      1. n 元钱必须正好用光，即7a+4b+3c=n
      2. 在满足以上条件情况下，成套的数量尽可能大，即a,b,c 中的最小值尽可能大。
      3. 在满足以上条件情况下，物品的总数尽可能大，即a+b+c 尽可能大。

      请你帮助禾木求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。

      -分析-

      题目要求a，b，c的最小值尽可能大，所以就要让它们的最小值越接近n/14越好。如果a，b，c的最小值为n/14 时无解，则让a,b,c的最小值为n/14−1，以此类推，直到有解为止；

      这下枚举范围小了不止一点，

      妈妈再也不用担心我TLE了！

      -代码-

      #include <bits/stdc++.h>
using namespace std;
int a, b, c, n, ans;
int main()// by AGOMG
{
    cin >> n;
    for(a = n / 14; a >= 0; a--)
        for(b = a; b <= n / 4; b++)
            for(c = a; c <= n / 3; c++)
                if(a * 7 + b * 4 + c * 3 == n)
                    {
                        cout << a << ' ' << b << ' ' << c << endl;
                        return 0;
                    }
    cout << -1 <<endl;
    return 0;
}
      • 4
        @ 2023-3-25 0:43:55 
        #include <iostream>
#include <algorithm>
using namespace std;

int n;

int main(void)
{

	cin>>n;
	
	if(n == 0)
	{
	    cout<<"0 0 0"<<endl;
	    return 0;
	}
	
	for(int p=n/14;p>=0;p--)
	{
			for(int j=p;j<=n/4;j++)
				for(int k=p;k<=n/3;k++)
					if(p*7+j*4+k*3 == n)
					{
						cout<<p<<" "<<j<<" "<<k<<endl;
						return 0;
					}
	}
	
	cout<<"-1"<<endl;
	return 0;
}
        • 2
          @ 2024-5-12 20:58:39

          AC放心食用.

          #include <bits/stdc++.h>
using namespace std;
int n,a,b,c;
int main()
{
    cin >> n;
    for (a = n/14;a >= 0;a--)
    {
        for (b = a;b <= n;b ++)
        {
            for (c = a;c <= n;c ++)
            {
                if (7*a+4*b+3*c==n)
                {
                    cout << a << " " << b << " " << c;
                    return 0;
                }    
            }
        }
    }
    cout << -1;
    return 0;
}
          • 2
            @ 2024-3-17 22:35:49

            循环枚举+判断（循环时减枝） 终于解决了😄

            using namespace std;
int n, a = -100000000, b = -100000000, c = -100000000, sum;
bool flag = false, m = false;
int main()
{
    cin >> n;
    for (int i = 0; i <= n/7; i++)
        for (int j = 0; j <= (n-7*i)/4; j++)
            for (int k = 0; k <= (n-7*i-4*j)/3; k++)
            {
                
                if (7*i + 4*j + 3*k == n)
                {
                    if (m == false)
                    {
                        a = i;
                        b = j;
                        c = k;
                        m = true;
                        flag = true;
                    }
                    
                    if (min(i, min(j, k)) > min(a, min(b, c)))
                    {
                        a = i;
                        b = j;
                        c = k;
                        sum = a+b+c;
                    }
                    else if (min(i, min(j, k)) == min(a, min(b, c)))
                    {
                            if (i+j+k >sum)
                            {
                                a = i;
                                b = j;
                                c = k;
                                sum = a+b+c;
                            }
                    }
                }
            }
    if (flag) cout << a << ' ' << b << ' ' << c;
    else cout << -1;
    return 0;
}
            • 2
              @ 2024-3-15 19:53:44 
              #include <iostream>//hetao819473
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}
              • 2
                @ 2023-10-29 15:37:57

                C2每课一题解（第四课 第二题）！！！

                这题需用枚举做法。

                话不多说，上代码！

                1.骗分

                #include <bits/stdc++.h>
using namespace std;
int a, b, c, d, n;
int main()
{
    cout<<"-1";
}

                对一个点

                image

                2.正解

                #include <iostream>
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}
                • 0
                  @ 2024-5-19 21:44:49

                  AC

                  #include <iostream>//hetao3097453
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;****
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}

                  很简单

                  • 0
                    @ 2024-1-6 17:28:38 
                    #include <iostream>
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}
                    • 0
                      @ 2023-10-30 20:26:02

                      #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; for(int a=n/14;a>=0;a--){//因为一套价格是14，因为尽可能大。a是最贵的，肯定要买了b或c才会存在a，所以直接n/14 ，a值就是最大，需要a-- for(int b=a;b<=n/4;b++){//因为a的价格最贵，所以买的数量肯定最少。b和c都要从a值开始。因为b的单价是4，所以最大范围值是n/4 for(int c=a;c<=n/3;c++){ //跟b道理一样。 if(7a+4b+3*c==n){//需要判断总价是否等于n。 cout<<a<<" "<<b<<" "<<c; return 0; } } } } cout<<"-1"; return 0; }

                      • 0
                        @ 2023-10-6 21:10:19 
                        #include <iostream>
using namespace std;
bool flag = false;
int main()
{
    int n;
    cin >> n;
    for(int a = n / 14;a >= 0;a--)
    {
        for(int b = a;b <= n / 3;b++)
        {
            for(int c = a;c <= n / 3;c++)
            {
                if(7 * a + 4 * b + 3 * c == n)
                {
                    cout << a << " " << b << " " << c << endl;
                    return 0;
                }
            }
        }
    }
    cout << "-1";
    return 0;
}
                        • 0
                          @ 2023-10-1 21:35:41

                          #include <iostream>//hetao 4900398 using namespace std; int main () { int n; bool flag = false; cin >> n; for( int a = n / 14 ; a >= 0 ; a-- ) { for( int b = a ; b <= n / 3 ; b++ ) { for( int c = a ; c <= n / 3 ; c++ ) { if( 7 * a + 4 * b + 3 * c == n) { cout << a << " " << b << " " << c ; return 0; } } } } cout << "-1"; return 0; }

                          • 0
                            @ 2023-10-1 21:35:22

                            #include <iostream>//hetao 4900398 using namespace std; int main () { int n; bool flag = false; cin >> n; for( int a = n / 14 ; a >= 0 ; a-- ) { for( int b = a ; b <= n / 3 ; b++ ) { for( int c = a ; c <= n / 3 ; c++ ) { if( 7 * a + 4 * b + 3 * c == n) { cout << a << " " << b << " " << c ; return 0; } } } } cout << "-1"; return 0; }

                            • 0
                              @ 2023-8-5 19:57:03

                              题解

                              #include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n;
    bool flag = false;
    cin >> n;
    for( int a = n / 14 ; a >= 0 ; a-- )
    {
        for( int b = a ; b <= n / 3 ; b++ )
        { 
            for( int c = a ; c <= n / 3 ; c++ )
            { 
                if( 7 * a + 4 * b + 3 * c == n)
                { 
                    cout << a << " " << b << " " << c ;
                    return 0; 
                } 
            }
        } 
    }
    cout << "-1";
    return 0;
}
                              • -1
                                @ 2024-3-14 23:13:24

                                不明白为什么n = 5的时候，答案是-1。看了前面的答案，补全了这个case，才过的。

                                #include <bits/stdc++.h>
using namespace std;

int main()
{
    int n = 5;
    cin >> n;

    if (n == 0)
    {
        cout << 0 << " " << 0 << " " << 0 << endl;
    }
    else if (n == 1 || n == 2)
    {
        cout << "-1";
        return 0;
    }
    else if (n == 5)
    {
        cout << "-1";
        return 0;
    }
    int res_a, res_b, res_c;
    bool is_flag = false;
    int min_value1 = -1;
    int min_value2 = -1;
    for (int a = n / 14; a >= 0; a--)
    {
        for (int c = a; c <= n / 3; c++)
        {
            int b = (n - 7 * a - 3 * c) / 4;
            if (b < 0)
            {
                continue;
            }

            if (a * 7 + b * 4 + c * 3 == n)
            {
                is_flag = true;
                min_value1 = max(min_value1, min(a, min(b, c)));
            }
            else
            {
                min_value2 = max(min_value1, min(a, min(b, c)));
            }
        }
    }
    if (is_flag)
    {
        int max_sum = -1;
        for (int a = n / 14; a >= 0; a--)
        {
            for (int c = a; c <= n / 3; c++)
            {
                int b = (n - 7 * a - 3 * c) / 4;
                if (b < 0)
                {
                    continue;
                }

                if (a * 7 + b * 4 + c * 3 == n && min(a, min(b, c)) == min_value1)
                {
                    if (a + b + c > max_sum)
                    {
                        max_sum = a + b + c;
                        res_a = a;
                        res_b = b;
                        res_c = c;
                    }
                }
            }
        }
        cout << res_a << " " << res_b << " " << res_c << endl;
        return 0;
    }
    else
    {
        res_a = 0;
        res_b = 0;
        res_c = 0;
        int max_sum = -1;
        for (int a = n / 14; a >= 0; a--)
        {
            for (int c = a; c <= n / 3; c++)
            {
                int b = (n - 7 * a - 3 * c) / 4;
                if (b < 0)
                {
                    continue;
                }

                if (a * 7 + b * 4 + c * 3 < n && min(a, min(b, c)) == min_value2)
                {
                    if (a + b + c > max_sum)
                    {
                        max_sum = a + b + c;
                        res_a = a;
                        res_b = b;
                        res_c = c;
                    }
                }
            }
        }
        cout << res_a << " " << res_b << " " << res_c << endl;
        return 0;
    }
    cout << "-1";
    return 0;
}
                                • -1
                                  @ 2023-8-6 22:01:36 
                                  #include <cstdio>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=n/14;i>=0;i--){
        for(int j=i;j<=n/3;j++){
            for(int k=i;k<=n/3;k++){
                if(7*i+4*j+3*k==n){
                    printf("%d %d %d\n",i,j,k);
                    return 0;
                }
            }
        }
    }
    printf("-1\n");
    return 0;
}
                                  • -7
                                    @ 2023-8-6 19:42:02

                                    #include<bits/stdc++.h> using namespace std; int main(){

                                    return 0;

                                    }

                                    • -12
                                      @ 2023-6-3 17:53:07

                                      #include<iostream> using namespace std; bool flag = false; int main () { int n ; cin >> n; for (int a = n / 14 ; a >= 0 ; a --) { for (int b = a ; b <= n / 3 ; b ++) { for (int c = a ; c <= n / 3 ; c ++) { if (7 * a + 4 * b + 3 * c == n) { cout << a << " " << b << " " << c ; return 0; } } } } cout << "-1"; return 0; }

                                      • 1

                                      【挑战题】文具采购

                                      信息

                                      ID
                                      45
                                      时间
                                      1000ms
                                      内存
                                      256MiB
                                      难度
                                      5
                                      标签
                                      递交数
                                      3343
                                      已通过
                                      1246
                                      上传者
                                      1. 关于
                                      2. 联系我们
                                      3. 隐私
                                      4. 服务条款
                                      5. 版权申诉
                                      6. Language
                                      7. 兼容模式
                                      8. 主题
                                      3. Worker 0, 36ms
                                      4. Powered by Hydro v4.9.24 Community, Modified by hetao