Logo 贾永菁的博客

博客

标签

今日打卡题222思路

2022-05-01 16:14:49 By 贾永菁

由于这题的标签是斐波那契数列。

所以我们不妨先找找规律

第一站和第二站没什么规律,所以我们从第3站找起

我们可以得出一个表

设第二站上车b人

得出下表

站 1 2 3 4 5 6 7 8 9 10

上车 a b a+b a+2b 2a+3b ······

下车 0 b b a+b a+2b ······

车上 a a 2a 2a+b 3a+2b ······

前两站车内人数 2a 3a 4a+b ······

我们来考虑一下第四行与第三行的关系

从第四站看起,你发现了什么?

    4            5

     2a+b         3a+2b 

     3a+0b             4a+1b

很明显可以发现 第四行a的个数比第三行多1,而b的个数少

我们设sum1为a的个数 sum1[i]表示第i站a的个数

sum2为b的个数,sum2[i]不用我说了。

可得出

sum1[i]=sum1[i-1]+sum1[i-2]-1(因为第四行是前两站车上人数和)

sum2[i]=sum2[i-1]+sum2[i-2]+1;(同上)

那么有了这个式子可以来推b

根据题目条件和上述公式可推出

asum1[n-1]+bsum2[n-1 ]=m;

把b挪出来得到

bsum2[n-1]=m-asum1[n-1]

化简得

b=(m-a*sum1[n-1])/sum2[n-1]

a和b都有了

答案也就出来了

我绿了!!!

2022-04-30 21:51:34 By 贾永菁

rating值1700了 我排到榜二啦!

1044

2022-04-28 19:54:19 By 贾永菁

include

using namespace std;

long long n,A,B;

long long a[999999];

bool check(long long m)

{

long long sum=0;

for(long long i=0;i<n;i++)

{

    long long j=a[i]-A*m;

    if(j<=0)

        continue;

    else

    {

        sum+=j/B;

        if(j%B!=0)

            sum++;

    }

}

if(sum<=m)

    return 1;

else

    return 0;

}

int main()

{

cin>>n>>A>>B;

for(long long i=0;i<n;i++)

    cin>>a[i];

sort(a,a+n);

long long l=1,r=a[n-1],ans,m;

while(l<=r)

{

    m=(l+r)/2;

    if(check(m))

    {

        r=m-1;

        ans=m;

    }

    else

        l=m+1;

}

cout<<ans;

return 0;

}

#183

2022-04-25 18:59:36 By 贾永菁

include

using namespace std;

int sum=0;

void get2(int n)

{

if(n%10==2)

    sum++;

if(n/10>0)

    return get2(n/10);

}

int main()

{

int a,b;

cin>>a>>b;

for(int i=a;i<=b;i++)

    get2(i);

cout<<sum;

}

帮助新人#14

2022-04-25 18:57:47 By 贾永菁

14

include

using namespace std;

int m,s,n;

bool cmp(int a,int b)

{

return a>b;

}

int main()

{

cin>>m>>s>>n;

int a[n],b[99999];

for(int i=0;i<n;i++)

    cin>>a[i];

sort(a,a+n);

for(int i=0;i<n-1;i++)

    b[i]=a[i+1]-a[i]-1;

int sum=a[n-1]-a[0];

sort(b,b+n-1,cmp);

for(int i=0;i<m-1;i++)

    sum-=b[i];

cout<<sum+1;

return 0;

}

帮助新人#13

2022-04-25 18:54:55 By 贾永菁

13

include

using namespace std;

int main()

{

int n,k,sum=0,money=0;


cin>>n>>k;


int a[k],b[k];


for(int i=0;i<k;i++)


cin>>a[i]>>b[i];


for(int i=0;i<k;i++)


{
      for(int j=i+1;j<k;j++)
      {
            if(a[j]<a[i])
          {
               swap(a[i],a[j]);
               swap(b[i],b[j]);
          }
      }
 }
 for(int i=0;i<k;i++)
 {
     if(n-sum>=b[i])
    {
        sum+=b[i];
        money+=a[i]*b[i];
    }
    else
    {
        int j=n-sum;
        money+=a[i]*j;
        break;
    }
}
cout<<money;
return 0;

}

一个崩溃边缘的程序猿

2021-12-18 19:11:46 By 贾永菁

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!

怎么写啊!!!!1

共 27 篇博客