Codeforces Round #510 (Div. 2)(C)

传送门:Problem C

https://www.cnblogs.com/violet-acmer/p/9682082.html

题意：

　　给你n个数，定义有两种操作

　　① 1 i j : (i != j) 将a[i]从数列中移除，且a[j] <- a[i]*a[j]

　　② 2 i : 将a[i]从数列中移除，此操作最多使用一次

　　注意：将数移除后剩余数的编号并未改变，依旧为初始时的输入顺序

　　在经过n-1次操作后使剩余的数最大

题解：

　　使用操作②的情况：

　　(1) : 数列中含有0

　　(2) : 负数个数为奇数个

　　n-1个操作的最终结果为负数个数为偶数个，数列中没有0元素（当然除去全是0元素这一情况）

踩坑：

　　如果此数列中有负数为奇数个，且含有0元素

　　处理方法：

　　(1)先将所有0元素通过操作①使其个数变为一个;

　　(2)在通过操作①用最大的负数乘以0，去除一个负数两两相乘后对结果贡献最小的负数，使负数个数为偶数个;

　　(3)通过②操作去除0元素

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=2e5+10;
 6 
 7 int n;
 8 int a[maxn];
 9 int neg,zero,pos;
10 int pos0[maxn];
11 int posNeg;//the position of the max negative number
12 bool vis[maxn];
13 
14 void Reader()
15 {
16     scanf("%d",&n);
17     neg=zero=pos=0;
18     posNeg=0;
19     memset(vis,false,sizeof vis);
20     for(int i=1;i <= n;++i)
21     {
22         scanf("%d",a+i);
23         if(a[i] > 0)
24             pos++;
25         else if(a[i] < 0)
26         {
27             neg++;
28             posNeg=(posNeg == 0 || a[i] > a[posNeg] ? i:posNeg);
29         }
30         else
31         {
32             zero++;
33             pos0[zero]=i;
34         }
35     }
36 }
37 void Process()
38 {
39     int ope=0;//操作数
40     if(zero != 0)//跳出此if语句后 zero == 0 || zero == 1
41     {
42         while(zero != 1)
43         {
44             printf("1 %d %d
",pos0[zero],pos0[zero-1]);
45             vis[pos0[zero]]=true;
46             zero--;
47             ope++;
48         }
49     }
50     if(ope == n-1)
51         return ;
52     if(neg&1)//如果负数个数为奇数个，通过去除一个值最大的奇数或乘以0来使奇数个数变为偶数
53     {
54         if(zero == 1)//如果存在0，则让值最大的负数乘以0
55         {
56             printf("1 %d %d
",posNeg,pos0[1]);//posNeg与pos0[1]顺序不可颠倒
57             ope++;
58             neg--;
59             if(ope < n-1)
60             {
61                 printf("2 %d
",pos0[1]);
62                 vis[pos0[1]]=true;
63                 ope++;
64             }
65         }
66         if(ope == n-1)
67             return ;
68         if(neg&1)//如果 zero == 0,则需要通过删除值最大的负数来使负数个数变为偶数
69         {
70             printf("2 %d
",posNeg);
71             neg--;
72             ope++;
73         }
74         vis[posNeg]=true;
75     }
76     else if(zero == 1 && ope < n-1)
77     {
78         printf("2 %d
",pos0[1]);
79         vis[pos0[1]]=true;
80         ope++;
81     }
82     if(ope == n-1)
83         return ;
84 
85     int num[maxn];
86     int index=0;
87     for(int i=1;i <= n;++i)
88         if(vis[i] != true)
89             num[++index]=i;
90     for(int i=1;i < index;++i)
91         printf("1 %d %d
",num[i],num[i+1]);
92 }
93 int main()
94 {
95     Reader();
96     Process();
97 }

View Code