欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Codeforces 1073D】Berland Fair

程序员文章站 2022-05-09 15:09:08
...

【链接】 我是链接,点我呀:)
【题意】


题意

【题解】


我们可以从左到右枚举一轮。
定义一个cost表示这一轮花费的钱数
如果cost+a[i]<=T那么就可以买它,并且买下它(模拟题目要求)
那么我们累计这一轮可以买下的数量cnt
则显然我们不用每一层都这么枚举
直接累加答案就好
ans = ans + T/cost cnt;
然后令T=T%cost就好了
因为newT = beforeT%cost
所以newT = beforeT-x
cost <cost
cost(1+x)>beforeT
cost>beforeT/(1+x)
xcost>xbeforeT/(1+x)
xcost>beforeT/(1/x+1)
x>=1
显然x越大,右边越来越大
则x
cost>beforeT/2
则newT<=beforeT/2
那么T的值每次都会除2.
所以复杂度就是O(n*log2T)的了

【代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5;
const long long M = 15e6;

int n;
ll T,ans = 0;
int a[N+10];

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> T;
    for (int i = 1;i <= n;i++) cin >> a[i];
    while (1){
        ll sum = 0;
        int cnt = 0;
        for (int i = 1;i <= n;i++){
            if (sum+a[i]>T){
                continue;
            }else{
                cnt++;
                sum = sum + a[i];
            }
        }
        if (cnt==0) break;
        ans = ans + T/sum*cnt;
        T = T%sum;
    }
    cout<<ans<<endl;
    return 0;
}