这个题要求乘积最小，显然我们希望乘积是负数是最好的，然后就是让这个负数的绝对值尽可能的大。
对于一堆数相乘，绝对值最小的对这个结果影响是最大的，所以我们就每次让绝对值最小的，如果是正数就加上x，负数就减去x，用个优先队列维护绝对值就可以了。
1 #include<iostream>神奇的代码
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<algorithm>
6 #include<cmath>
7 #include<queue>
8 #include<vector>
9 using namespace std;
10 const int mo=1e9+7;
11 priority_queue<long long>qwq;
12 priority_queue<long long>qaq;
13 int n,k,x,tmp;
14 long long ans;
15 int main(){
16 scanf("%d%d%d",&n,&k,&x);
17 if (k==0){
18 ans=1;
19 for (int i=1,tmp;i<=n;i++){
20 scanf("%d",&tmp);
21 ans=(ans*tmp)%mo;
22 }
23 printf("%lld\n",(ans+mo)%mo);
24 return 0;
25 }
26 tmp=0;
27 long long b=0,a=0,c=0,d=0;
28 for (int i=1;i<=n;i++){
29 scanf("%lld",&a);
30 if (a>=0) qwq.push(-a);
31 else qaq.push(a);
32 }
33 if (qaq.size()%2==0){
34 if (qaq.size()==0){
35 b=-qwq.top();
36 qwq.pop();
37 while ((tmp<k)&&(b>=0)) {b-=x;tmp++;}
38 if (b<0)
39 qaq.push(b);
40 else qwq.push(-b);
41 }
42 else{
43 c=-qaq.top();
44 if (qwq.empty())
45 d=1e10;
46 else
47 d=-(qwq.top());
48 if (c<d){
49 b=-c;
50 qaq.pop();
51 while ((tmp<k)&&(b<=0)) {b+=x;tmp++;}
52 if (b>=0)
53 qwq.push(-b);
54 else qaq.push(b);
55 }
56 else{
57 b=d;
58 qwq.pop();
59 while ((tmp<k)&&(b>=0)) {b-=x;tmp++;}
60 if (b<0)
61 qaq.push(b);
62 else qwq.push(-b);
63 }
64 }
65 }
66 while (tmp<k){
67 c=-(qaq.top());
68 if (qwq.empty())
69 d=1e10;
70 else
71 d=-(qwq.top());
72 if (c<d){
73 b=-c;
74 b=b-x;
75 qaq.pop();
76 qaq.push(b);
77 tmp++;
78 }
79 else{
80 b=d;
81 b=b+x;
82 qwq.pop();
83 qwq.push(-b);
84 tmp++;
85 }
86 }
87 ans=1;
88 while (qwq.size()){
89 d=-qwq.top();
90 ans=ans*(d%mo)%mo;
91 qwq.pop();
92 }
93 while (qaq.size()){
94 c=qaq.top();
95 ans=ans*(c%mo)%mo;
96 qaq.pop();
97 }
98 printf("%lld\n",(ans+mo)%mo);
99 return 0;
100 }
这是个巨长的代码...我傻傻地将正数和负数分开来处理......其实有个更简短的....
1 #include<cstdio>简短的代码
2 #include<queue>
3 #include<cmath>
4 using namespace std;
5 int n,k,x;
6 int a[400000];
7 long long ans=1;
8 const int mo=1e9+7;
9 struct node{
10 int data,id;
11 bool operator < (const node & temp) const
12 {
13 return abs(data) > abs(temp.data);
14 }
15 };
16 priority_queue <node> qwq;
17 int tmp=1;
18 int main(){
19 scanf("%d%d%d",&n,&k,&x);
20 for (int i=1;i<=n;i++){
21 scanf("%d",&a[i]);
22 if (a[i]<0) tmp=-tmp;
23 qwq.push(node{a[i],i});
24 }
25 while (k--){
26 node t=qwq.top();qwq.pop();
27 if (a[t.id]<0){
28 if (tmp==-1) a[t.id]-=x;else a[t.id]+=x;
29 if (a[t.id]>=0) tmp=-tmp;
30 }
31 else {
32 if (tmp==-1) a[t.id]+=x; else a[t.id]-=x;
33 if (a[t.id]<0) tmp=-tmp;
34 }
35 qwq.push(node{a[t.id],t.id});
36 }
37 for (int i=1;i<=n;i++) ans=(ans*a[i])%mo;
38 printf("%lld\n",(ans+mo)%mo);
39 }