题目描述
给定 n 个整数 a1…an。
有 n+2 个位置：0, 1, 2, …, n, n+1。
你初始时在 0 位置，每次你可以选择以下其中一种操作：
向右移动一格，代价为 1。
向左移动一格，代价为 1。
传送回 0 位置或者 n+1 位置（自己决定去哪），记你当前的位置为 i，则传送的代价为 ai。注意：每个位置只能发动一次传送。也就是说，若你某次在 i 处发动传送，则再此之后到达 i 位置时不能选择传送操作。
问总代价不超过 c 时，最多能发动几次传送。
输入格式
第一行一个整数 T 代表数据组数。
每组数据第一行两个整数代表 n 和 c，第二行 n 个数表示 a1 到 an。
输出格式
每组数据输出一行，代表答案。
样例
Input 1
10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000
Output 1
2
3
0
1
3
2
1
1
2
2
样例不过求调
#include<bits/stdc++.h>
using namespace std;
long long a[200005],sum[200005];
struct date{
long long id,value;
}b[200005];
bool cmp(date x,date y){return x.value<y.value;}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int n,c;
cin>>n>>c;
for(int i=1;i<=n;++i){
cin>>a[i],b[i].value=a[i]+min(i,n-i+1);
b[i].id=i;
}
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+b[i].value;
int ans=0;
for(int i=1;i<=n;++i){
int l=0,r=n;
if(a[i]+i>c) continue;
while(l<r){
int mid=(l+r+1)/2;
long long w=sum[mid]+a[i]+i;
if(mid>=b[i].id)
w-=b[b[i].id].value;
if(w<=c) l=mid;
else r=mid-1;
}
if(l<b[i].id) ++l;
ans=max(ans,l);
}
cout<<ans<<'\n';
}
return 0;
}