【链接】 我是链接,点我呀:)
【题意】
题意
【题解】
我们可以从左到右枚举一轮。
定义一个cost表示这一轮花费的钱数
如果cost+a[i]<=T那么就可以买它,并且买下它(模拟题目要求)
那么我们累计这一轮可以买下的数量cnt
则显然我们不用每一层都这么枚举
直接累加答案就好
ans = ans + T/cost cnt;
然后令T=T%cost就好了
因为newT = beforeT%cost
所以newT = beforeT-xcost <cost
cost(1+x)>beforeT
cost>beforeT/(1+x)
xcost>xbeforeT/(1+x)
xcost>beforeT/(1/x+1)
x>=1
显然x越大,右边越来越大
则xcost>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;
}