Dolce Vita time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
Turbulent times are coming, so you decided to buy sugar in advance. There are n shops around that sell sugar: the i-th shop sells one pack of sugar for ai coins, but only one pack to one customer each day. So in order to buy several packs, you need to visit several shops.
Another problem is that prices are increasing each day: during the first day the cost is ai, during the second day cost is ai+1+1, during the third day — ai+2+2 and so on for each shop i.
On the contrary, your everyday budget is only x coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding x. Note that if you don't spend some amount of coins during a day, you can't use these coins during the next days.
Eventually, the cost for each pack will exceed x, and you won't be able to buy even a single pack. So, how many packs will you be able to buy till that moment in total?
InputThe first line contains a single integer t (1≤t≤10001≤≤1000) — the number of test cases. Next t cases follow.
The first line of each test case contains two integers n and x (1≤n≤2⋅1051≤≤2⋅105; 1≤x≤1091≤≤109) — the number of shops and your everyday budget.
The second line of each test case contains n integers a1,a2,…,an1,2,…, (1≤ai≤1091≤≤109) — the initial cost of one pack in each shop.
It's guaranteed that the total sum of n doesn't exceed 2⋅1052⋅105.
OutputFor each test case, print one integer — the total number of packs you will be able to buy until prices exceed your everyday budget.
Example input Copy 4 3 7 2 1 2 5 9 10 20 30 40 50 1 1 1 2 1000 1 1 output Copy11 0 1 1500Note
In the first test case,
- Day 1: prices are [2,1,2] You can buy all 33 packs, since 2+1+2≤7
- Day 2: prices are [3,2,3] You can't buy all 33 packs, since 3+2+3>7, so you buy only 22 packs.
- Day 3: prices are [4,3,4] You can buy 22 packs with prices 4 and 3.
- Day 4: prices are [5,4,5] You can't buy 22 packs anymore, so you buy only 1 pack.
- Day 5: prices are [6,5,6] You can buy 1 pack.
- Day 6: prices are [7,6,7] You can buy 1 pack.
- Day 7: prices are [8,7,8] You still can buy 11 pack of cost 77.
- Day 8: prices are [9,8,9]. Prices are too high, so you can't buy anything.
In the second test case, prices are too high even at the first day, so you can't buy anything.
In the third test case, you can buy only one pack at day one.
//本质是贪心,每天所有的价值都+1,一开始想的是差分和前缀和,但是差分好像不太行,因为是整体区间
//考虑贪心,每天都要+1,利用前缀和,从后向前枚举,找到最多可以买的糖果数,利用ans作为天数维护前缀和
//有以下性质: s+day*i<=num才可以,然后从这个数目出发,看看这个数目能撑几天
//有以下方程: 能撑的天数=num-s[i]-++day*i,然后计入总数 糖果数=(能撑的天数+最开始的天数)*现在的糖果数
//最后更新天数,现在得天数=1+当前糖果数能撑的天数
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
long long n,t,a[N],f[N],res,num,ans,s[N];
bool vis[N];
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>n>>num;
res=0,ans=0;
for(int i=1;i<=n;i++) cin>>s[i];
sort(s+1,s+1+n);
for(int i=1;i<=n;i++) s[i]+=s[i-1];//前缀和
for(int i=n;i>=1;i--){
if(s[i]+ans*i>num) continue;
//利用ans来维护前缀和
long long cnt=((num-s[i]-ans*i)/i)+1;
res+=cnt*i;
ans+=cnt;
}
cout<<res<<endl;
}
return 0;
}
标签：buy,Dolce,packs,each,prices,Vita,day,pack From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17513358.html