題目

模擬

首先想到模擬。
但是看到數據范圍，模擬不了。

#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記錄