codeforces 1042C Array Product【构造】
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目：戳这里
题意：n个数，两种操作，第一种是a[i]*a[j],删掉a[i],第一种是直接删除a[i]（只能用一次）剩下的数序列号不变。操作n-1次，使最后剩下的那个数最大化。
解题思路：
正数之间全用操作1得到的结果最大。
负数的个数如果是偶数，全用操作1最后得到的也最大。如果是奇数，那最大的那个负数（贪心的思想）就要进行特殊操作，具体怎么操作要看后面有没有0，如果有0就用操作1去乘，没有就用操作2直接给这个数删了。
有0的话就把所有的0乘最后一个0，然后把最后一个0删了。
附ac代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn = 5e5 + 10;
5 const int inf = 5e5 + 10;
6 struct nod
7 {
8 ll a;
9 int id;
10 }nu[maxn];
11 bool cmp(nod x, nod y)
12 {
13 return x.a < y.a;
14 }
15 int main() {
16 int n;
17 scanf("%d", &n);
18 for(int i = 1; i <= n; ++i)
19 {
20 scanf("%lld", &nu[i].a);
21 nu[i].id = i;
22 }
23 sort(nu + 1, nu + 1 + n, cmp);
24 int cntm = 0;
25 int lastz = 0;
26 int cntop = 0;
27 int firstp = 0;
28 int firstz = 0;
29
30 for(int i = 1; i <= n; ++i)
31 {
32 if(nu[i].a < 0) ++cntm;
33 if(nu[i].a == 0)
34 {
35 if(!firstz) firstz = i;
36 lastz = i;
37 }
38 if(nu[i].a > 0)
39 {
40 firstp = i;
41 break;
42 }
43 }
44 if(cntm & 1)
45 {
46 if(lastz) firstz = cntm;
47 else printf("2 %d\n", nu[cntm].id);
48 --cntm;
49 }
50 for(int i = 1; i < cntm; ++i)
51 {
52 printf("1 %d %d\n", nu[i].id, nu[cntm].id);
53 }
54 for(int i = firstz; i < lastz; ++i)
55 {
56 printf("1 %d %d\n", nu[i].id, nu[i + 1].id);
57 }
58 if(lastz && (cntm || firstp))//这里wa了好多发
59 {
60 printf("2 %d\n", nu[lastz].id);
61
62 }
63 if(firstp)
64 {
65 if(cntm)
66 {
67 printf("1 %d %d\n", nu[cntm].id, nu[n].id);
68 }
69 for(int i = firstp; i < n; ++i)
70 {
71 printf("1 %d %d\n", nu[i].id, nu[n].id);
72 }
73 }
74 return 0;
75 }
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |