Inhabitant of the Deep Sea

用户11039529

发布于 2024-04-25 18:52:06

770

发布于 2024-04-25 18:52:06

文章被收录于专栏：算法学习日常算法学习日常

题目：Inhabitant of the Deep Sea

题目描述：

输入：

输出

样例：

输入：

输出：

思路：

AC代码：

题目：Inhabitant of the Deep Sea

题目描述：

𝑛 艘飞船出发探索海洋深处。这些飞船的编号从 1 到 𝑛 ，依次递增；第 𝑖 艘飞船的耐久度为 𝑎𝑖 。

克拉肯按照特定顺序攻击了这些飞船 𝑘 次。首先，它攻击第一艘飞船，然后是最后一艘，接着又是第一艘，以此类推。

克拉肯的每次攻击都会使飞船的耐久度降低 1 。当船只的耐久度下降到 0 时，它就会沉没，不再受到攻击(因此船只不再是第一艘或最后一艘，卡拉基只攻击尚未沉没的船只)。如果所有的船只都沉没了，克拉肯也就没有什么可攻击的了，于是它就游走了。

例如，如果 𝑛=4 、𝑘=5 和 𝑎=[1,2,4,3] ，就会发生以下情况：

卡拉基攻击第一艘飞船，它的耐久度变为零，现在为 𝑎=[2,4,3] ；
卡拉基攻击最后一艘飞船，现在为 𝑎=[2,4,2] ；
克拉肯攻击第一艘飞船，现在为𝑎=[1,4,2] ；
克拉肯号攻击最后一艘飞船，现在是 𝑎=[1,4,1] ；
克拉肯攻击第一艘飞船，其耐久度变为零，现在为 𝑎=[4,1] 。

克拉肯攻击后有多少艘船被击沉？

输入：

第一行包含一个整数 t𝑡 ( 1≤𝑡≤10^4 ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 𝑛 和 𝑘 ( 1≤𝑛≤2⋅10^5 , 1≤𝑘≤10^15 )--船只数量和克拉肯攻击船只的次数。

每个测试用例的第二行包含 𝑛 个整数𝑎1,𝑎2,…,𝑎𝑛 ( 1≤𝑎𝑖≤10^9 ) --船只的耐用性。

保证所有测试用例的 𝑛 之和不超过2⋅10^5 。

输出

对于每个测试用例，另起一行输出被克拉肯击沉的船只数量。

样例：

输入：

输出：

思路：

用两个指针，指向当前第一个和最后一个，再对其进行操作,具体看代码

AC代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
ll a[N];

int main()
{
	ll l, r;
	int t;
	cin >> t;
	while (t--)
	{
		ll n, k, i;
		cin >> n >> k;
		for (i = 0; i < n; i++)
			cin >> a[i];

		l = 0;
		r = n - 1;
		ll k1 = k % 2;//操作在第一个元素的次数
		if (k1)//如果k是奇数
			k1 = k / 2 + 1;
		else
			k1 = k / 2;
		ll k2 = k / 2;//操作在最后一个元素的次数

		int countx = 0;//记录答案
		while (l <= r && (k1 > 0 || k2 > 0))
		{
			if (k1 >= a[l])
			{
				k1 -= a[l];
				a[l] = 0;
				countx++;
				if (l == r)
					break;//注意break，不然最后判断k2 >= a[r]时会重复计数
				l++;
			}
			else
			{
				a[l] -= k1;
				k1 = 0;
			}
			if (k2 >= a[r])
			{
				k2 -= a[r];
				r--;
				countx++;
			}
			else
			{
				a[r] -= k2;
				k2 = 0;
			}
		}
		cout << countx << endl;
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-24，如有侵权请联系 cloudcommunity@tencent.com 删除

break