自动搬运

查看原文

来自洛谷，原作者为

	lzqy_ 生而绚烂，璀璨如花。

搬运于2025-08-24 22:21:20，当前版本为作者最后更新于2020-04-28 17:17:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不用数组的优化做法

题意：

有$n$只宝可梦，每只宝可梦需要$ki$个果子来升级，共有$mi$个果子，每次升级之后能返还$2$个果子。

输出所有宝可梦一共升了几级，并输出升级最多的宝可梦的名字。

分析

这道题的关键在于计算每只宝可梦可以升几级。

我们先假设不会返还$2$个果子，那能够升几级？ 很明显，升$mi/ki$ 级，还剩下 $mi$%$ki$ 个果子。而每升一级就返回$2$个果子，所以果子数还要再加上升级级数乘二，即$mi+=(mi/ki)*2$。

但是这就结束了吗？很明显还不行。因为加上奖励的果子之后，也许还可以再升级。所以，以上的过程我们要执行多次，直到无法升级为止。

代码如下：

while(k<=m)
{
   sum+=m/k;//此处的sum为升级级数
   m=((m/k)*2)+m%k;
   //新的果子数量为'剩下的果子+奖励的果子'
 }

优化

（注：这一段讲的内容不用也可以AC，只是能够进一步地优化）

• 还记得上文的$(mi/ki)*2$ 吗？此处的$*2$可以用位运算来进行优化，即$<<1$。

• 我们不必把每一只宝可梦升级级数用数组记录下来。我们在处理的时候，可以边处理边求最大值 。

• 用快读进一步优化读入速度。

代码实现

结合代码一起来看看吧~

#include <bits/stdc++.h>
using namespace std;
inline int read()                        
//以字符串形式读入数字可提速（具体详情看上方链接）
{
  int x=0;
  char c=getchar();
  for(; c<'0'  || c>'9';  c=getchar());
  for(; c<='9' && c>='0'; c=getchar())
    x=(x<<3)+(x<<1)+c-'0';   
    //位运算优化即x*8+x*2=x*10
  return x;
}
int main()
{
  string ans2,name;
  int k,m,mmax=0,sum,ans1=0,n;//别忘了初始化
  n=read();//快读
  while(n--)//循环处理每一只宝可梦
  {
    sum=0;//别忘记每次刷新sum初值
    cin>>name;
    k=read();
    m=read();
    while(k<=m)
    {
      sum+=m/k;
      m=((m/k)<<1)+m%k;//基本位运算优化
    }//求升级级数
    ans1+=sum;//总升级级数增加
    if(mmax<sum)//如果升级级数最多
    {
      mmax=sum;
      ans2=name;
    }//更新最大值以及宝可梦名字
  }
  cout<<ans1<<"\n"<<ans2;//输出
  return 0;//结束
}

祝大家AC愉快~