D. Maxim and Array（贪心+优先队列）

题目链接：D. Maxim and Array

input

5 3 1
5 4 3 5 2

output

5 4 3 5 -1

input

5 3 1
5 4 3 5 5

output

5 4 0 5 5

input

5 3 1
5 4 4 5 5

output

5 1 4 5 5

input

3 2 7
5 4 2

output

5 11 -5

题意：给你一个长度为n的数组，然后你可以在对数组中的每个数增加或者减少x，但是这种操作最多只能用k次。
问操作之后，要保证数组之积最小，输出操作之后数组每位的值。
思路：先判断整个数组中负数的个数，如果有偶数个负数，那么我们可以选择绝对值最小的那个数，让它的符号转变，因为负数肯定大于正数，所以我们要保证一定有奇数个负数，（不能转变的，就让绝对值小的更小就行了（因为不能转换，说明最后的乘积一定是正数，我们让最小的更小是可以减少乘积的）
在我们保证有奇数个负数之后，我们就需要使数组的每个数的绝对值乘积最大（因为是负数，绝对值越大，数值越小）我们假设数组中有两个数a,b；并且$a<b.$a<b.
$(a+x)*b>(b+x)*a$(a+x)∗b>(b+x)∗a负数反过来同理。
所以我们要每次改变数组中绝对值最小的那个，这时候就用优先队列来维护数组绝对值最小值。（还有要保证输出答案要对应数组编号，我刚开始没注意，wa了一发，懵逼了好久）。

#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define LL long long
const int N=2e5+10;
struct zxc
{
    LL x,y,id;
    friend bool operator < (zxc q,zxc w)
    {
        return q.x>w.x;
    }
}a[N],b[N];
bool cmp(zxc s,zxc d)
{
    return s.id<d.id;
}
priority_queue<zxc>q;
int main()
{
   LL n,m,w;
   LL flog=0;
   scanf("%lld%lld%lld",&n,&w,&m);
   for(LL i=1;i<=n;i++)
   {
       scanf("%lld",&a[i].y);
       if(a[i].y<0)
       {
           a[i].x=-a[i].y;
           flog++;
       }
       else
       {
           a[i].x=a[i].y;
       }
       a[i].id=i;
       q.push(a[i]);
   }
   zxc k;
   if(flog%2==0)
   {
       k=q.top();
       q.pop();
       if(k.y<0)
       {
           LL num=abs(k.y)/m+1;
           if(w>=num)
           {
              w-=num;
              k.y+=num*m;
           }
           else
           {
               k.y+=w*m;
               w=0;
           }
           k.x=abs(k.y);
          // printf("%d******\n",num);
       }
       else
       {
           LL num=k.y/m+1;
           if(w>=num)
           {
              w-=num;
              k.y-=num*m;
           }
           else
           {
               k.y-=w*m;
               w=0;
           }
           k.x=abs(k.y);

       }
       q.push(k);
   }

   for(LL i=1;i<=w;i++)
   {
       k=q.top();
       q.pop();
       if(k.y<0)
       {
           k.y-=m;
           k.x+=m;
       }
       else
       {
           k.y+=m;
           k.x+=m;
       }
       q.push(k);
   }
   LL num=1;
   while(!q.empty())
   {
       b[num++]=q.top();
       q.pop();
   }
   sort(b+1,b+num,cmp);
   for(LL i=1;i<num;i++)
   {
     printf("%lld ",b[i].y);
   }
   printf("\n");
    return 0;
}
/*
2 1 10
-10 -10
*/