CF1073D Berland Fair

洛谷 CF1073D Berland Fair

洛谷传送门

题意翻译

第十一届Berland博览会马上就会开始！博览会中有nn个摊位，这些摊位围成一个圆圈，也就是说1号摊位与2号摊位相邻、2号摊位与3号摊位相邻……n号摊位与1号摊位相邻。每个摊位都在出售糖果（这也是够奇葩的），但是摊位之间的价格可能不同，第ii个摊位中糖果的价格为a_{i}*a**i*，每个摊位里都有无限数量的糖果出售（Unlimited candy works!）

Polycarp带了TT块钱去展览，他准备这么参观博览会：

• 他从11号摊位开始参观
• 每当他路过一个摊位时，如果他买得起这个摊位里的糖果，他会买一个
• 无论他有没有买糖果，他都会按照顺时针前往下一个摊位

当他一个糖果都买不起的时候，他会离开博览会。

输出Polycarp最终买了多少个糖果。

n ≤ 2 * 10^5n≤2∗105， 1 ≤ T ≤ 10 ^ {18}1≤T≤1018 1 ≤ a_{i} ≤ 10^91≤*a**i*≤109

题目描述

XXI Berland Annual Fair is coming really soon! Traditionally fair consists of nn booths, arranged in a circle. The booths are numbered 11 through nn clockwise with nn being adjacent to 11 . The ii -th booths sells some candies for the price of a_i*a**i* burles per item. Each booth has an unlimited supply of candies.

Polycarp has decided to spend at most TT burles at the fair. However, he has some plan in mind for his path across the booths:

• at first, he visits booth number 11 ;
• if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately;
• then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not).

Polycarp's money is finite, thus the process will end once he can no longer buy candy at any booth.

Calculate the number of candies Polycarp will buy.

输入格式

The first line contains two integers nn and TT ( 1 \le n \le 2 \cdot 10^51≤n≤2⋅105 , 1 \le T \le 10^{18}1≤T≤1018 ) — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains nn integers a_1, a_2, \dots, a_na1,a2,…,*a**n* ( 1 \le a_i \le 10^91≤*a**i≤109 ) — the price of the single candy at booth number ii* .

输出格式

Print a single integer — the total number of candies Polycarp will buy.

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

说明/提示

Let's consider the first example. Here are Polycarp's moves until he runs out of money:

1. Booth 11 , buys candy for 55 , T = 33T=33 ;
2. Booth 22 , buys candy for 22 , T = 31T=31 ;
3. Booth 33 , buys candy for 55 , T = 26T=26 ;
4. Booth 11 , buys candy for 55 , T = 21T=21 ;
5. Booth 22 , buys candy for 22 , T = 19T=19 ;
6. Booth 33 , buys candy for 55 , T = 14T=14 ;
7. Booth 11 , buys candy for 55 , T = 9T=9 ;
8. Booth 22 , buys candy for 22 , T = 7T=7 ;
9. Booth 33 , buys candy for 55 , T = 2T=2 ;
10. Booth 11 , buys no candy, not enough money;
11. Booth 22 , buys candy for 22 , T = 0T=0 .

No candy can be bought later. The total number of candies bought is 1010 .

In the second example he has 11 burle left at the end of his path, no candy can be bought with this amount.

---

题解：

不太明白这题为啥是个紫题

题目大意：

给定一个长度为\(N\)的序列，有一个数\(K\)，每次遍历序列时如果\(K\ge a_i\)，那么，\(ans++\)，\(K-=a_i\)。如果位置为\(N\)，下一次遍历会返回\(1\).问\(ans\)最后是多少。

（来自国赛金牌集训队大佬\(Winniechen\)的模拟赛）

考试的时候就想到了这样的思路：

先跑前缀和，然后比较\(K\)和\(sum[N]\)的值，以\(N\)为单位来跑，这样就省时间，什么时候不能继续减了，就一直从\(1-N\)跑，直到\(K\)一个数也不能再减为止，输出\(ans\)，有了下面这份代码：

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=2*1e5+1;
ll n,k,ans,minn=1e9+10;
ll a[maxn];
ll sum[maxn];
int main()
{
    //freopen("fairs.in","r",stdin);
    //freopen("fairs.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
        minn=min(minn,a[i]);
    }
    while(k>=sum[n])
    {
        ans+=n;
        k-=sum[n];
    }
    while(k>=minn)
    {
        for(int i=1;i<=n;i++)
            if(k>=a[i])
            {
                ans++;
                k-=a[i];
            }
    }
    printf("%lld",ans);
    return 0;
}

期望得分：100，实际得分：100.

但是机房有很多大佬不相信本蒟蒻能切这道题，所以他们来check了我的代码，后来分析复杂度，得出我的确切不掉这题，只是\(Winniechen\)的数据很水罢了。不服气的我找到了原题提交...

然后T了。（真香）

后来苦思冥想，思路没有变，但是想到了这份暴力枚举代码的种种优化：

首先，不用跑前缀和，因为我们只能用到\(sum[N]\)，开前缀数组纯属浪费空间。

其次，不用用while循环一次一次减，只需要用一个乘法算式即可。

然后，不用每次都从\(1 - N\)枚举，因为如果\(K\)不能减去这个数，它就永远也不可能再能减去这个数，所以用标记数组，碰到减不下去的就直接标记，以后遍历的时候就可以跳过了。

为了实现以上思路，需要用一个”死循环“以及一个flag变量标记，具体细节不讲了，请看官们直接欣赏代码：

#include<cstdio>
#define ll long long
using namespace std;
const int maxn=1e5*2+1;
ll n,k;
ll a[maxn];
bool v[maxn];
ll sum,ans,tot;
int main()
{
    scanf("%lld%lld",&n,&k);
    tot=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    while(1)
    {
        ans+=tot*(k/sum);
        k%=sum;
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            if(v[i])
                continue;
            if(k>=a[i])
            {
                ans++;
                k-=a[i];
                flag=1;
            }
            else
            {
                v[i]=1;
                sum-=a[i];
                tot--;
            }
        }
        if(flag==0)
            break;
    }
    printf("%lld",ans);
    return 0;
}