NOIp (on line) 入门组 2020 总结

 

  得分情况 :

        估分:

          100+30+30=160;

        实际:

          95+70+25=190;


  T1 :

     题意:

          有n块钱,买三种文具,分别为 a:7元、b:4元、c:3元,问怎么买能让n元钱全部用完,而且使 min(a,b,c) 最大,满足以上条件后再使a+b+c最大。如果钱无论如何都用不完就输出-1。

     数据范围:

          1≤n≤105


  分析:

      直接暴力!!!

      分别枚举a,b,c,输出最佳结果。

      但光枚举肯定会爆掉,要优化一下。我们看到n元必须全部用完,那么就只枚举a,b,再通过 c=(n-a*7-b*4)/3 算出c。因为钱必须用完,所以 (n-a*7-b*4)/3 应该没有余数。

      接下来我们再把a和b的枚举过程优化,总价钱肯定不能超n,所以a得从0枚举到n/7,剩下的钱就枚举b了,所以b的从0枚举到n-a*7。结束。


 

  代码如下:

//我的代码   95分 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main()
{
    int n,Min=0,ra,rb,rc,res=0;
    scanf("%d",&n);
    for(int a=0;a*7<=n;a++)
    {
        for(int b=0;b*4<=n-a*7;b++)
        {
            if((n-(7*a+4*b))%3==0)
            {
                int c=(n-(7*a+4*b))/3;
                int i=min(min(a,b),c),j=a+b+c;
                if(i>Min)
                {
                    Min=i,res=j;
                    ra=a,rb=b,rc=c;
                }
                else if(i==Min&&j>res)
                {
                    res=j;
                    ra=a,rb=b,rc=c;
                }
                
            }
        }
    }
    if(n==0) puts("0 0 0"); 
    else
    if(!Min&&!res) puts("-1");
    else
    printf("%d %d %d",ra,rb,rc);
}

//我的满分代码    
//说实话 没看出有啥不同 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main()
{
    int n,Min=0,ra,rb,rc,res=0;
    scanf("%d",&n);
    for(int a=0;a*7<=n;a++)
    {
        for(int b=0;b*4<=n-a*7;b++)
        {
            if((n-(7*a+4*b))%3==0)
            {
                int c=(n-(7*a+4*b))/3;
                int i=min(min(a,b),c),j=a+b+c;
                if(i>Min)
                {
                    Min=i,res=j;
                    ra=a,rb=b,rc=c;
                }
                else if(i==Min&&j>res)
                {
                    res=j;
                    ra=a,rb=b,rc=c;
                }
                
            }
        }
    }
    if(n==0) puts("0 0 0");
    else
    if(!Min&&!res) puts("-1");
    else
    printf("%d %d %d",ra,rb,rc);
}

  T2:

      数据太大,只会用DP骗一下分。QAQ


  T3:

      不会,只会写正常的最短路。QAQ


 


    ~END~

上一篇:[AH2017/HNOI2017] 单旋 - Splay


下一篇:set、multiset深度探索