当前位置：首页 > news >正文

CF1660D Maximum Product Strikes Back 题解

news 2025/7/8 23:02:58

CF1660D Maximum Product Strikes Back 题解

题目描述
输入格式
输出格式
样例 #1
- 样例输入 #1
- 样例输出 #1
思路点拨（分类题）
- 缩小研究对象范围
- 除0的分析
- 加上0的分析
代码实现
小方法陈述

题目描述

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

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

输入格式

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

对于每个小测试点

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

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

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

输出格式

对于每个测试点输出共一行，包含2个非负整数 $x$ 和 $y$ ( $\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

思路点拨（分类题）

缩小研究对象范围

题目中限定了 $-2\leq a_i\leq 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;
}