codeforces1042C. Array Product(构造+思维)

题目链接: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;
}

发表留言

人生在世,错别字在所难免,无需纠正。