CodeForces 1024C. Array Product(模拟)(分类讨论)

题意:给定一个长度为n(2 <= n <= 3e5)的数组\(a[i](-1e9 <= a[i] <= 1e9)\)，n和a[i]都是整数。你的任务是留下一个可以尽可能最大的数字。你可以进行n - 1次下面的操作直到留下一个最大的数字。
操作1:选择一对下标(i, j)满足(1 <= i, j <= n, i != j)。j位置上的数变成了i位置和j位置上的数的乘积，\(a[j] = a[j] * a[i]\)，并且i位置上的数被删除。

操作2:选择一个位置i，把位置i上的数字删除(i位置的数不复存在，以后的操作中无法被选中)。操作2最多一次

输出一个可行的方案即可。

分析:分类讨论，这道题我写复杂了，我把所有的情况都列举出来。但是有一种更好的分类方法，如下:

ps:对于一些删除容器中的操作，我们可以用一个数组标记哪些数被删除了(懒标记)。如果我们想用一个数组中指定的数，我们可以再开一个容器保存要用的数的下标。

我的复杂代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 300005;
const int inf = 0x3f3f3f3f;
int a[N];
int main()
{
	//有正数
	bool flag1 = false;
	//有负数
	bool flag2 = false;
	//有零
	bool flag3 = false;
	//负数的个数
	int cnt = 0;
	//绝对值最小的负数，它的坐标
	int mx = inf, pos = 0;
	//存储正数、负数、零的坐标
	vector<int> p1, p2, p3;
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		if (a[i] > 0) flag1 = true, p1.push_back(i);
		if (a[i] < 0)
		{
			flag2 = true, p2.push_back(i), ++cnt;
			if (mx > abs(a[i]))
			{
				mx = abs(a[i]), pos = i;
			}
		}
		if (a[i] == 0) flag3 = true, p3.push_back(i);
	}

	//只有0
	if (!flag1 && !flag2 && flag3)
	{
		for (int i = 0; i < p3.size() - 1; ++i)
			printf("1 %d %d\n", p3[i], p3[i + 1]);
	}//只有正数
	else if ((flag1 && !flag2 && !flag3))
	{
		for(int i = 0; i < p1.size() - 1; ++i)
			printf("1 %d %d\n", p1[i], p1[i + 1]);
	}//只有正数和0
	else if ((flag1 && !flag2 && flag3))
	{
		for(int i = 0; i < p3.size() - 1; ++i)
			printf("1 %d %d\n", p3[i], p3[i + 1]);
		printf("2 %d\n", p3[p3.size() - 1]);
		for (int i = 0; i < p1.size() - 1; ++i)
			printf("1 %d %d\n", p1[i], p1[i + 1]);
	}
	else
	{
		int leftpos = -1;
		//奇数个负数
		if (cnt & 1)
		{
			vector<int> p4;
			for (int i = 0; i < p2.size(); ++i)
				if (p2[i] != pos) p4.push_back(p2[i]);
			if (cnt != 1)
			{
				for (int i = 0; i < p4.size() - 1; ++i)
					printf("1 %d %d\n", p4[i], p4[i + 1]);
				leftpos = p4[p4.size() - 1];
			}
		}
		else
		{			
			for (int i = 0; i < p2.size() - 1; ++i)
				printf("1 %d %d\n", p2[i], p2[i + 1]);
			leftpos = p2[p2.size() - 1];
		}
		//只有负数
		if (!flag1 && !flag3)
		{
			if (cnt & 1) printf("2 %d\n", pos);
		}
		else
		{
			//有负数有正数有0
			if (flag1 && flag3)
			{
				if (cnt & 1)
				{
					for (int i = 0; i < p3.size() - 1; ++i)
						printf("1 %d %d\n", p3[i], p3[i + 1]);
					printf("1 %d %d\n", pos, p3[p3.size() - 1]);
					printf("2 %d\n", p3[p3.size() - 1]);
					if(leftpos != -1)
						printf("1 %d %d\n", leftpos, p1[0]);
					for (int i = 0; i < p1.size() - 1; ++i)
						printf("1 %d %d\n", p1[i], p1[i + 1]);
				}
				else
				{
					for (int i = 0; i < p3.size() - 1; ++i)
						printf("1 %d %d\n", p3[i], p3[i + 1]);
					printf("2 %d\n", p3[p3.size() - 1]);
					if(leftpos != -1)
						printf("1 %d %d\n", leftpos, p1[0]);
					for (int i = 0; i < p1.size() - 1; ++i)
						printf("1 %d %d\n", p1[i], p1[i + 1]);
				}
			}//有负数和0
			else if (!flag1 && flag3)
			{
				if (cnt & 1)
				{
					int leftzero;
					for (int i = 0; i < p3.size() - 1; ++i)
						printf("1 %d %d\n", p3[i], p3[i + 1]);
					leftzero = p3[p3.size() - 1];
					printf("1 %d %d\n", pos, leftzero);
					if(cnt != 1)
						printf("2 %d\n", leftzero);
				}
				else
				{
					for (int i = 0; i < p3.size() - 1; ++i)
						printf("1 %d %d\n", p3[i], p3[i + 1]);
					if(cnt != 0)
						printf("2 %d\n", p3[p3.size() - 1]);
				}
			}//有负数和正数
			else
			{
				if (cnt & 1)
				{
					printf("2 %d\n", pos);
					if (leftpos != -1)
					{
						printf("1 %d %d\n", leftpos, p1[0]);
					}				
					for (int i = 0; i < p1.size() - 1; ++i)
						printf("1 %d %d\n", p1[i], p1[i + 1]);
				}
				else
				{
					if (leftpos != -1)
					{
						printf("1 %d %d\n", leftpos, p1[0]);
					}
					for (int i = 0; i < p1.size() - 1; ++i)
						printf("1 %d %d\n", p1[i], p1[i + 1]);
				}

			}
		}
	}

	return 0;
}

CodeForces 1024C. Array Product(模拟)(分类讨论)

原文：https://www.cnblogs.com/pixel-Teee/p/13282908.html