题解：CF1042C Array Product

一个不太简单的分类讨论。

容易发现，答案只用分讨负数数量和零数量的奇偶性，因为正数总是要选的。

还有一个性质，题目说我们只能删除一个数字其实是假的，我们想删多少都可以，只要把这些数都乘在一起就可以了。

有些负数需要选，因为负负得正，众所周知。

零也有时候需要选，比如说答案是负数。

所以我们开始分类讨论：

有零
- 奇数个负数
  
  我们把最大的负数和零合并在一起删掉，然后把其他正数和负数合并。
- 偶数个负数
  
  把所有零删掉就可以了。
无零
- 奇数个负数
  
  把多出去一个最大的负数删掉，然后合并其他所有数。
- 偶数个负数
  
  不用删除，合并所有数。

综上，我们把所有数的下标塞到

3

个数组里面就行了。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005];
vector<int> zero,num,b;
bool cmp(int q,int h)
{
	return a[q]>a[h];
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0) zero.push_back(i);
		else if(a[i]<0) num.push_back(i); 
		else b.push_back(i);
	}//有0的情况
	if((int)zero.size()>0)
	{
		if((int)num.size()%2==0)//偶数
		{
			for(int i=1;i<zero.size();i++)
			{
				cout<<1<<" "<<zero[i-1]<<" "<<zero[i]<<"\n";
			}
			if(num.size()>0||b.size()>0) cout<<2<<" "<<zero[zero.size()-1]<<"\n";
			for(int i=1;i<num.size();i++)
			{
				cout<<1<<" "<<num[i-1]<<" "<<num[i]<<"\n";
			}
			if(num.size()>0&&b.size()>0) cout<<1<<" "<<num[num.size()-1]<<" "<<b[0]<<'\n';
			for(int i=1;i<b.size();i++)
			{
				cout<<1<<" "<<b[i-1]<<" "<<b[i]<<"\n";
			}
		}
		else//奇数
		{
			for(int i=1;i<zero.size();i++)
			{
				cout<<1<<" "<<zero[i-1]<<" "<<zero[i]<<"\n";
			}
			sort(num.begin(),num.end(),cmp);
			cout<<1<<" "<<zero[zero.size()-1]<<" "<<num[0]<<"\n";
			if(b.size()+num.size()-1>0) cout<<2<<" "<<num[0]<<"\n";
			for(int i=2;i<num.size();i++)
			{
				cout<<1<<" "<<num[i-1]<<" "<<num[i]<<"\n";
			}
			if(num.size()>1&&b.size()>0) cout<<1<<" "<<num[num.size()-1]<<" "<<b[0]<<'\n';
			for(int i=1;i<b.size();i++)
			{
				cout<<1<<" "<<b[i-1]<<" "<<b[i]<<"\n";
			}
		}
		return 0;
	}
	int q=0;
	sort(num.begin(),num.end(),cmp);
	if(num.size()%2==1)//多出的负数
	{
		cout<<2<<" "<<num[0]<<"\n";
		q=1;
	}
	for(int i=0;i<b.size();i++) num.push_back(b[i]);
	for(int i=q+1;i<num.size();i++) cout<<1<<" "<<num[i-1]<<" "<<num[i]<<"\n";
	return 0;
}

题解：CF1042C Array Product

文章操作

相关推荐

评论

题解：CF1042C Array Product