【 Educational Codeforces Round 53 (Rated for Div. 2) D. Berland Fair】思维题

D. Berland Fair

题意

$有n个商品排列成一行，每个商品有一个加个a[i]，最初你身上有T元$
$每次都从左到右走，如果买的起这个商品就买一件，买不起就不买$
$每次走到头就重新从左端走，问最后能买到多少件商品$
$n<=2?10^{5}1<=T<=10^{18}$

做法

$由于T比较大，我们肯定要用到除法$
$每次我们统计当前可买的商品的价值总和now$
$若T>now,则下次遍历一次所有商品还是这么买$
$否则我们就重新判断当前可以购买哪些商品$
$但是我们要考虑所有商品都小于T，但是不能一起购买的数据$
$我们就要从前往后模拟一遍更新一次T$
$再重新统计所有小于T的商品的价值和$
$最后直到一个物品也购买不了退出循环$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
ll a[maxn];
int main()
{
    int n;ll T;scanf("%d%lld",&n,&T);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);ll ans=0;while(T){
    ll sum=0;ll cnt=0;for(int i=1;i<=n;i++){
    if(a[i]<=T){
    cnt++;sum+=a[i];}}if(cnt==0) break;if(T<sum){
    for(int i=1;i<=n;i++){
    if(T>=a[i]){
    ans++;T-=a[i];}}}else{
    ans+=1LL*cnt*(T/sum);T=T%sum;}}printf("%lld\n",ans);return 0;
}