时间限制: 1000ms
空间限制: 524288kB
题目描述
给定 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
样例解释
无
数据范围
1≤T≤2×10^5
1≤n≤2×10^5
1≤c,ai≤10^9
∑n≤2×10^5
样例没过可是死活调不出来
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,pair<int,int> >//.first存在该点传送+离0,n+1距离 .second.first存传送需要能量
.second.second存原下标
#define F first
#define S second
using namespace std;
int t,n,c,ans,qzh[200005];PII a[200005];//qzh 前缀和
signed main()
{
cin >> t;
while (t--)
{
cin >> n >> c;ans = 0;
for (int i=1;i<=n;i++) cin >> a[i].S.F,a[i].F = a[i].S.F+max(i,n+1-i),a[i].S.S = i;
sort(a+1,a+n+1);
for (int i=1;i<=n;i++) qzh[i] = qzh[i-1]+a[i].F;
for (int qwq=1;qwq<=n;qwq++)//遍历一开始去哪里
{
int l=0,r=n,e=c-a[qwq].S.F-a[qwq].S.S;//e 现能量
if (e<0) continue;
while (l<r)//二分次数
{
int mid = (l+r+1)/2;int w = qzh[mid];
if (mid>=qwq) w -= a[qwq].F;
if (e>=w) l = mid; else r = mid-1;
}
ans = max(ans,l+(qwq>l));
}
cout << ans << endl;
}
return 0;
}