题解 P6494 【[COCI2016-2017#2] Go】
不用数组的优化做法
题意：
有
输出所有宝可梦一共升了几级，并输出升级最多的宝可梦的名字。
分析
这道题的关键在于计算每只宝可梦可以升几级。
我们先假设不会返还
但是这就结束了吗？很明显还不行。因为加上奖励的果子之后，也许还可以再升级。所以，以上的过程我们要执行多次，直到无法升级为止。
代码如下：
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;//结束
}