CF1955C Inhabitant of the Deep Sea 题解

题目

模拟

首先想到模拟。
但是看到数据范围，模拟不了。

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define int long long
#define lhs printf("\n");
using namespace std;
const int N=1e5+10;
const int M=2024;
const int inf=0x3f3f3f3f;
int t;
int k,n;
int a[N];
int s,e;
int num;
int ans;
int sum1[N],sum2[N];
signed main()
{scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){sum1[i]=sum1[i-1]+a[i];}num=ans=0;s=1;e=n;while(num<k and s<=e){a[s]--;num++;if(a[s]<=0){s++;ans++;}if(s>e)break;if(num>=k){ break;}a[e]--;num++;	if(a[e]<=0){e--;ans++; }}printf("%lld\n",ans);}return 0;
}

会TLE

思路

首先模拟的复杂度是o(k)的
k巨大，那么我们模拟不了。
就要想o(n)的解决方法
因为海妖是前面打一下，后面打一下。
所以我们可以把击打次数分成两份，前面一份，后面一份。
注意：当k为偶数时，前后数量相通，否则前面一份比后面一份多1。

做法

用前缀和与后缀和数组。
分别寻找满足小于等于当前方向的那一份之中最大的位置。
找出两个坐标算出答案。

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define int long long
#define lhs printf("\n");
using namespace std;
const int N=3e5+10;
const int M=2024;
const int inf=0x3f3f3f3f;
int t;
int k,n;
int a[N];
int s,e;
int num;
int ans;
int sum1[N],sum2[N];
int sum;
int flag1;
int flag2;
int h;
signed main()
{scanf("%lld",&t);while(t--){memset(sum1,0,sizeof sum1);memset(sum2,0,sizeof sum2);sum=ans=0;scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum+=a[i];if(k>=sum){printf("%lld\n",n);continue;}for(int i=1;i<=n;i++){sum1[i]=sum1[i-1]+a[i];}for(int i=n;i>=1;i--){sum2[i]=sum2[i+1]+a[i];}h=k/2;flag1=0;flag2=n+1;for(int i=1;i<=n;i++){if(sum2[i]<=h){flag2=i;break;}}if(k%2!=0)h++;for(int i=n;i>=1;i--){if(sum1[i]<=h){flag1=i;break;}}printf("%lld\n",flag1+n-flag2+1);}return 0;
}

AC记录