Loading...

CF1073D [Berland Fair]

check评论:0 条 remove_red_eye浏览量:535 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-26

昨晚$cf$只切了四道题的蒟蒻来写个题解

这道题很简单啊...比$C$简单多了

首先我们考虑暴力枚举,一个一个转圈圈,肯定是超时

然后大家都会想到一个优化,就是把所有点的总和找到,然后找当前钱可以把一圈买多少遍,然后把钱对总和取模再暴力救星

可是这样会被卡死,如果我只有一个的价钱是$1e8$,其他都是$1$,暴力极限还是会循环$1e8$次左右

我们接着前面的思路,如果当前点的价钱已经大于剩下的钱数,我们就把$sum$减去这个点的价钱,再用刚才的方法,把剩下的钱除以这个值,看其他的东西还能够买几圈,然后取模就行了qwq

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,t;
ll a[200020];
ll sum;
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    ll ans=0;
    ll pp=t/sum;
    ans+=pp*n;
    t=t-pp*sum;
    int flag=0;
    int i=1;
    int now=n;
    while(1)
    {
        if(i==1)
        {
            flag=0;
        }
        if(a[i]<=t)
        {
            t-=a[i];
            flag=1;
            ans++;
        }
        else
        {
            sum-=a[i];
            if(!sum)
            {
                break;
            }
            now--;
            ll qaq=t/sum;
            ans+=now*qaq;
            t=t-qaq*sum;
        }
        if(i==n&&!flag)
        {
            break;
        }
        else if(i==n)
        {
            i=1;
            continue;
        }
        i++;
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名