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

D. Berland Fair

题意

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

做法

$由于T比较大，我们肯定要用到除法$由于T比较大，我们肯定要用到除法
$每次我们统计当前可买的商品的价值总和now$每次我们统计当前可买的商品的价值总和now
$若T&gt;now,则下次遍历一次所有商品还是这么买$若T>now,则下次遍历一次所有商品还是这么买
$否则我们就重新判断当前可以购买哪些商品$否则我们就重新判断当前可以购买哪些商品
$但是我们要考虑所有商品都小于T，但是不能一起购买的数据$但是我们要考虑所有商品都小于T，但是不能一起购买的数据
$我们就要从前往后模拟一遍更新一次T$我们就要从前往后模拟一遍更新一次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;
}