RT,反正也过不了了... test2怎么也过不去
#include <bits/stdc++.h>
using namespace std;
#define maxn 5000010
int t;
long long n, m;
long long a[maxn];
int num[maxn]; //存取其它选手的num
int num2[maxn]; //备份
int myNum = 0;
int myNum2 = 0;
int cur = 0;
int main() {
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];//存储每个人的准备时间
}
//然后开始分类讨论
int temp;
int temp1 = m;
for (int i = 1; i <= n; i++) {
num[i] = i;
num2[i] = i;
}
cur = 1;
myNum = 0;
while (cur <= n) {
if (m < a[cur]) {
cur++;
} else {
myNum++;
m -= a[cur];
num[cur]--; //败者次数减一
cur++;
}
}
sort(num + 1, num + n + 1);
int index = n + 1;
temp = 0;
int mingci = 1;
num[n + 1] = -maxn;
// cout << "myNum=" << myNum << endl;
for (int i = n; i >= 1; i--) {
if (num[i] < num[i + 1]) {
mingci += temp;
temp = 1;
} else {
temp ++;
}
// cout << "num[i]=" << num[i] << "mingci=" << mingci << "temp=" << temp << endl;
if (num[i] <= myNum) {
index = mingci;
break;
}
}
//倒着搜
myNum = 0;
cur = n;
m = temp1;
while (cur >= 1) { //从头往后搜,先找大的
if (m < a[cur]) {
cur--;
} else {
myNum++;
m -= a[cur];
num2[cur]--; //败者次数减一
cur--;
}
}
sort(num2 + 1, num2 + n + 1);
int index1 = n + 1;
temp = 0;
mingci = 1;
num2[n + 1] = -maxn;
// cout << "myNum=" << myNum << endl;
for (int i = n; i >= 1; i--) {
if (num2[i] < num2[i + 1]) {
mingci += temp;
temp = 1;
} else {
temp ++;
}
// cout << "num2[i]=" << num2[i] << "mingci=" << mingci << "temp=" << temp << endl;
if (num2[i] <= myNum) {
index1 = mingci;
break;
}
}
cout << min(index, index1) << endl;
}
return 0;
}