目录
题目:Inhabitant of the Deep Sea
题目描述:
输入:
输出
样例:
输入:
输出:
思路:
AC代码:
𝑛 艘飞船出发探索海洋深处。这些飞船的编号从 1 到 𝑛 ,依次递增;第 𝑖 艘飞船的耐久度为 𝑎𝑖 。
克拉肯按照特定顺序攻击了这些飞船 𝑘 次。首先,它攻击第一艘飞船,然后是最后一艘,接着又是第一艘,以此类推。
克拉肯的每次攻击都会使飞船的耐久度降低 1 。当船只的耐久度下降到 0 时,它就会沉没,不再受到攻击(因此船只不再是第一艘或最后一艘,卡拉基只攻击尚未沉没的船只)。如果所有的船只都沉没了,克拉肯也就没有什么可攻击的了,于是它就游走了。
例如,如果 𝑛=4 、𝑘=5 和 𝑎=[1,2,4,3] ,就会发生以下情况:
克拉肯攻击后有多少艘船被击沉?
第一行包含一个整数 t𝑡 ( 1≤𝑡≤10^4 ) - 测试用例的数量。
每个测试用例的第一行包含两个整数 𝑛 和 𝑘 ( 1≤𝑛≤2⋅10^5 , 1≤𝑘≤10^15 )--船只数量和克拉肯攻击船只的次数。
每个测试用例的第二行包含 𝑛 个整数𝑎1,𝑎2,…,𝑎𝑛 ( 1≤𝑎𝑖≤10^9 ) --船只的耐用性。
保证所有测试用例的 𝑛 之和不超过2⋅10^5 。
对于每个测试用例,另起一行输出被克拉肯击沉的船只数量。
6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2
2
3
5
0
2
2
用两个指针,指向当前第一个 和 最后一个,再对其进行操作,具体看代码
#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;
}