题目
链接：https://www.luogu.com.cn/problem/CF1955C
题解
思路：
- 海妖攻击船是一前一后，但如果按照这样循环必定超时，所以换个思路，可以先算出海妖攻击前、后的次数，然后分别扣除船的耐久度。
- 由于海妖是先攻击前面，所以可以让攻击后面的次数为可k2=k/2（由于会舍去后面小数），再让前面为可k1=k-k/2；如果上一艘船耐久度不够就让i++，并让r=i；直到耐久度够。
- 如果所有的船的耐久度都不够海妖打，就直接输出船数n。（我一开始是这样写的）或者让用r计数，如果后面的船损失超过了r（也就是从n开始的i--，使i<r），就停止计数。
- 最最最重要的是范围（我就是因为范围问题，一直优化其他地方，结果范围小了）用int肯定是不够大（别问我怎么知道的），所以我用long long int。
代码
点击查看代码
#include<iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int arr[200001] = { 0 };//船
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
int s = 0,r=0; //s表示沉船，r是前面沉船数量
int k1, k2;
k2 = k / 2;//攻击后面次数
k1 = k - k2;//攻击前面次数
for (int i = 1; i <= n; i++) {
if (k1 >= arr[i]) {
k1 -= arr[i];
r = i;
}
else {
arr[i] -= k1;
k1 = 0;
break;
}
}
s = r;//让s计入r的数
for (int i = n; i > r; i--) {
if (arr[i] <= k2) {
k2 -= arr[i];
s++;
}
else
break;
}
cout << s << endl;
}
}