CF1042C.Array Product（构造+贪心） 1700

题意

题目链接：Problem - 1042C - Codeforces
给你一个长度为n的数组a，你需要进行n-1个操作，使得最后的值最大：
- 1 i j 表示将$a_i$删除，$a_i\times a_j$重新赋值给$a_j$
- 2 i 将$a_i$删除 （最多只能用一次）

例如样例，只需要将0删除，其他进行1操作，任意符合操作的都可以。

思路

这种题做多了，首先想到如果有-1,-2,-3的时候，什么时候要删，要删什么？
首先需要判断负数的个数，例如是-2,-3那么就不需要删除了，因为负负得正。
然后如果要删，那么肯定是删最小的了。

那么这个题还有个问题所在就是，删除只能用一次，那么什么时候删？还有0特殊的时候怎么办？

只需要把0都放在一起当作一个垃圾桶，最后把要删的那个最小的也放在这个垃圾桶里面，先进行若干个1操作让垃圾桶里面的数都在最后那个值之后，再进行2操作删除。

恭喜！喜提wa，还有特殊情况：全是0的时候，不需要删了，因为它最后是需要数字的，全部删除相当于没有数字了，可能还有wa，那就边wa边改吧~

总结：将0和要删的放进垃圾桶，特殊判断

代码

vector<int> v0,v1;
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        if (a[i]<0)
        {
            if (a[i]>ans) ans = a[i], x = i;
            cnt++;
        }
        if (a[i]==0) 
            v0.push_back(i);
    }
    if (ans>-inf&&cnt%2==1) v0.push_back(x);
    else x = -inf;
    if (v0.size())
    {                                 
        int len = v0.size();
        for (int i=0;i<len-1;i++)
            cout<<1<<" "<<v0[i]<<" "<<v0[i+1]<<endl;
        if (len!=n)
            cout<<2<<" "<<v0.back()<<endl;
    }
    for (int i=1;i<=n;i++)
        if (a[i]!=0&&i!=x) v1.push_back(i);
    int len = v1.size();
    for (int i=0;i<len-1;i++)
        cout<<1<<" "<<v1[i]<<" "<<v1[i+1]<<endl;
}