Inhabitant of the Deep Sea

jumaoxiangrijui / 2024-07-13 / 原文

题目

链接：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;
	}
}