双指针|Codeforces Round #780 (Div. 3) D. Maximum Product Strikes Back(1600) c++|算法

Codeforces Round #780 (Div. 3) D. Maximum Product Strikes Back

【双指针|Codeforces Round #780 (Div. 3) D. Maximum Product Strikes Back(1600)】大致思路：一个双指针题型，细节很多。 0 0 0当作分割线使用，每个块里面单独计算，真正影响值的大小的是绝对值为 2 2 2的个数，所以我们如果更新最大值即在保证是正数的前提下更新最多的 2 2 2。

参考代码：

#include using namespace std; const int N = 2e5+10; int a[N]; int L,R; int sum; int n; int count(int l,int r){ int cnt=0; for(int i=l; i<=r; i++)if(a[i]<0)cnt++; return cnt; } void get(int l,int r){//比较大小进行更新 int ans=0; for(int i=l; i<=r; i++){ if(abs(a[i])==2)ans++; } if(ans>sum){ sum=ans; L=l-1,R=n-r; } } void cale(int l,int r){// 每一组单独拉出计算 int temp=count(l,r); //计算负数数量 if(temp%2==0){//全是正数直接判断 get(l,r); } else{//左边删和右边删+贪心思想 int l1=l; while(a[l1]>=0)l1++; get(l1+1,r); int r1=r; while(a[r1]>=0)r1--; get(l,r1-1); } } void solve(){ cin>>n; L=n,R=0; //初始化，全部删除情况 sum=0; for(int i=1; i<=n; i++)cin>>a[i]; a[n+1]=0; //分隔符 for(int i=1,j=1; i<=n+1; i++){ if(a[i]==0){ cale(j,i-1); j=i+1; } } cout<>t; while(t--){ solve(); } return 0; }