题目链接:codeforces1042C. Array Product
题意:给定n个数,然后给定两种操作:1)移除 i 位置的数,把 j 位置的数更新为 a[i]*a[j] ;2)移除 i 位置的数(该操作只能进行一次)。问进行怎样的 n-1 次操作后,能保证最后剩下的数最大。
题解:
如果是正数的话可以不用考虑;
如果是负数的话,两个较小的负数相乘能够得到较大的正数,注意判断负数的个数的奇偶性;
如果有 0 的话,可以用 操作1 一步一步的消至只剩 1 个0;
参考代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[200009];
bool used[200009];
int main()
{
scanf("%d",&n);
memset(used,0,sizeof(used));
bool sig=0;
for(int i=1; i<=n; i++)
{
scanf("%d",a+i);
if(a[i]>0)
used[i]=1;
else if(a[i]<0)
{
used[i]=1;
sig=!sig;
}
}
if(sig)
{
int id=-1;
for(int i=1; i<=n; i++)
if(a[i]<0&&(id==-1||a[i]>a[id]))
id=i;
used[id]=0;
}
int tot=0;
for(int i=1; i<=n; i++)
if(used[i])
tot++;
if(tot==0)
{
for(int i=1; i<=n; i++)
if(a[i]==0)
{
used[i]=1;
break;
}
}
int id1=-1,id2=-1;
for(int i=1; i<=n; i++)
if(used[i])
id1=i;
else
id2=i;
for(int i=1; i<=n; i++)
{
if(used[i])
{
if(id1!=i)
printf("1 %d %d\n",i,id1);
}
else if(id2!=i)
printf("1 %d %d\n",i,id2);
else
printf("2 %d\n",id2);
}
return 0;
}