#include<bits/stdc++.h>
#define ll long long
#define maxsize 200100
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int n;
ll t,sum,a[maxsize],ans,now;
int main()
{
while(cin>>n>>t)
{
sum=0;
ans=now=0;
for(int i=1;i<=n;++i) cin>>a[i];
while(1)
{
for(int i=1;i<=n;++i)
{
if(t>=a[i])
{
t-=a[i];
sum+=a[i];
ans++;
now++;
}
}
if(now==0) break;
ans+=t/sum*now;
t=t%sum;
now=0;sum=0;
}
cout<<ans<<endl;
}
return 0;
}
(code来源:https://blog.csdn.net/qq_38735931/article/details/83443583)
题意:
初始有t元,每次从1开始买,从1到n依次有n个人,每个人的东西价格为a[i],该人依次能买就买,到n之后再回到1从头开始,问最后能买到的东西数量(参考:http://www.cnblogs.com/myx12345/p/9858179.html)
code解释:(自己写的)
一开始如果按照正常的暴力的思路的话,就直接while(t>=min(a))
{
for(1->n):
if(t>=a[i]):
t-=a[i];
sum++;
}
cout<<sum<<endl;
这样就完事了,但是由于T是1e18非常大,所以绝对会TLE,所以需要换一种思路。
结合上面的CODE,发现,用两个循环:外循环控制是不是还能转圈,内循环控制统计能买到的个数。
注意两个特殊的数据:now,sum
注意ans的加的值有两个:t/sumnow,++1
现在来解释一下:
首先,now表示的是能买到的个数,sum表示能买到的所有价格的总和数。
ans加的第一个值是t/sum*now,这个表是什么意思?
这个表示的是,比如现在刚刚转完一圈,那么,我也统计了now,sum,那么为了减少循环的次数,我就要把当前的(now,sum)当作一个周期,随着我不断的转圈,周期的(now,sum)会不断减小,但是每一个周期的转圈次数不一定是一样的(在一个周期里面,now和sum都是一样的),这样,就可以用乘法原理直接把当前的ans加上t/sum(表示这个周期我能转几圈),之后乘上now(乘法原理,乘上这个周期的买到的东西的数量)
那还有一个++1又是什么呢?这个表示我在这一个周期的第一次转圈中,如果能买,就让ans+1;
之后就是整个程序的核心了:
t=t%sum,这个表示的是我消耗完这个周期,那么剩下的余数肯定会小于当前的sum,从而大大的降低了循环的次数,使得整个程序的时间复杂度变成了评测系统可以接受的程度。