CF1660D Maximum Product Strikes Back 题解

题目描述

你有一个长度为 $n$ 的数组，每一个元素都在 $-2$ 到 $2$ 的整数之间，当从数组首删去 $x$ 个元素，从数组末删去 $y$ 个元素时，数组剩下的乘积最大，输出 $x$ 和 $y$ 。

特别地，当存在多种情况时，输出任意一种即可； 当数组为空时，这个数组的乘积被认为是 $1$ 。

输入格式

第一行包含一个正整数 $t$ ($1\le t\le 10^4$) —小测试点的总数

对于每个小测试点

第一行包含一个正整数 $n$ ( $1\le n\le 2\cdot 10^5$ ) —$a$数组的总长度 .

下一行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$ ( $-2\le |a_i|\le 2$ ) — $a$数组的每个元素 .

保证 $\sum n\le 2\cdot 10^5$ .

输出格式

对于每个测试点输出共一行，包含2个非负整数 $x$ 和 $y$ ( $0\le x+y\le n$ ) — 使数组乘积最大的操作

样例 #1

样例输入 #1

5
4
1 2 -1 2
3
1 1 -2
5
2 0 -2 2 -1
3
-2 -1 -1
3
-1 -2 -2

样例输出 #1

0 2
3 0
2 0
0 1
1 0

思路点拨（分类题）

缩小研究对象范围

题目中限定了$-2\le a_i\le 2且为整数$限定了$a_i$的值只能为$-2,-1,0,1,2$

除0的分析

假设没有$0$的存在，应该怎么做？
非常容易发现删$1$并不会对数组绝对值符号有任何优劣影响，删$-1$只会控制数组乘积的符号，$2、-2$才是对于数组绝对值起绝对性影响。

因此得出除0之外的分析结论：

• 若数组乘积为正，不用删任何数
• 若数组乘积为负，则在数组收尾$2$边中选$|a_i|=2较少的一边删除其所在前缀或后缀$

加上0的分析

$\because$题目说明，若数组为空，默认乘积为$1$，所以$0$是坚决不能存在于数组之中，必须全部删除。
$\therefore$本题相当于拿$0$做挡板，把原数组分为很多细分的除0的区间，只需要对这部分取$|a_i|=2$较多的区间作为留下的数组即可

代码实现

#include<bits/stdc++.h>
using namespace std;const int maxn=2e5+10;
int t,n,cnt0,tot,ansl,ansr;
int a[maxn];
struct node{int u,v,dis;
}f[maxn];
//除0的情况
inline int solve(int l,int r){int num1=0,num2=0,mi2=maxn,mx2=0;for(int i=l;i<=r;i++){if(a[i]>0)++num1;else {++num2;mi2=min(mi2,i);mx2=i;}}if(num2%2==0){ansl=l-1;ansr=n-r;}else{int w1=0,w2=0;bool flag=false;for(int i=l;i<=mi2;i++){if(abs(a[i])==2)++w1;} for(int i=mx2;i<=r;i++){if(abs(a[i])==2)++w2;}if(w1>=w2){ansl=l-1;ansr=n-mx2+1;}else {ansl=mi2;ansr=n-r;}}int all=0;for(int i=ansl+1;i<=n-ansr;i++){if(abs(a[i])==2)++all;}return all;
}
inline bool cmp(node nx,node ny){return nx.dis>ny.dis;}
int main(){scanf("%d",&t); while(t--){cnt0=tot=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==0)++cnt0;}if(cnt0==n){printf("%d 0\n",n);continue;}if(n==1){if(1>=a[1])printf("1 0\n");else  printf("0 0\n");continue;}//有0的预处理分段+排序if(cnt0>0){int k=1,k1=n;while(a[k]==0)++k;while(a[k1]==0)--k1;int x=k,y=k;if(k==k1){f[++tot].u=x;f[tot].v=y;f[tot].dis=solve(f[tot].u,f[tot].v);f[tot].u=ansl;f[tot].v=ansr;}for(int i=k+1;i<=k1;i++){if(a[i-1]==0&&a[i]!=0)x=y=i;if(a[i]!=0&&a[i-1]!=0)++y;if(a[i]==0||i==k1){f[++tot].u=x;f[tot].v=y;f[tot].dis=solve(f[tot].u,f[tot].v);f[tot].u=ansl;f[tot].v=ansr;}		}sort(f+1,f+tot+1,cmp);printf("%d %d\n",f[1].u,f[1].v);}else {int o=solve(1,n);printf("%d %d\n",ansl,ansr);}}return 0;
} 

小方法陈述

• 应用背景：当CF的题目单测试点内的小测试点过多且单一，当某小测试点出现错误但因为省略隐藏，而不知道错误
  实践：可以去骗测试点，发现问题，不断进行历史修补论的内容，直到最后$AC$