题目链接：http://codeforces.com/problemset/problem/721/D
Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array ai either with ai + x or with ai - x. Please note that the operation may be applied more than once to the same position.
Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. 
)
can reach, if Maxim would apply no more than k operations to it. Please help him in that.
The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.
The second line contains n integers a1, a2, ..., an (
) —
the elements of the array found by Maxim.
Print n integers b1, b2, ..., bn in
the only line — the array elements after applying no more than k operations to the array. In particular, 
should
stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum
possible.
If there are multiple answers, print any of them.
5 3 1 5 4 3 5 2
5 4 3 5 -1
5 3 1 5 4 3 5 5
5 4 0 5 5
5 3 1 5 4 4 5 5
5 1 4 5 5
3 2 7 5 4 2
5 11 -5
题解：
1.首先在输入时，统计负数的个数，目的是知道初始状态的乘积是正数（包括0）还是负数。
2.如果乘积为正数，那么就需要减小某个数的绝对值，使其改变符号， 而且步数越少越好，由此推出：减少绝对值最小的那个数的绝对值，可以最快改变符号，使得乘积变为负数。
3.如果乘积已经为负，那么就需要增加某个数的绝对值， 使得乘积的绝对值尽可能大， 根据基本不等式： a+b>=2*根号（a*b），若要a*b的值最大，则a==b。 可以得出结论：当a与b的差值越小时，a*b越大。或者可以自己手动推算一遍， 也可以得出这个结论。由此推出：增加绝对值最小的那个数的绝对值，使得乘积的绝对值尽可能大。
4.总的来说：就是需要对绝对值最小的数进行操作。当乘积为正或为0时， 减小其绝对值，直到符号改变； 当乘积为负时， 增加其绝对值， 使其乘积的绝对值尽可能大。 用优先队列维护。
学习之处：
a+b=常数， 当a与b的差值越小时，a*b越大（a*b>=0）。
这里的a*b，可以假设a为绝对值最小的那个数， b为其他数的绝对值的乘积。所以这个结论也适用于多个数的乘积（将多个转为2个）。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <algorithm>
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
#define eps 0.0000001
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int maxn = 2e5+10;
struct node
{
LL v, s, pos;
bool operator<(const node&x)const{
return v>x.v;
}
};
priority_queue<node>q;
LL a[maxn], n, k, x, flag;
void init()
{
scanf("%lld%lld%lld",&n, &k, &x);
while(!q.empty()) q.pop();
flag = 0;
for(int i = 1; i<=n; i++)
{
node e;
scanf("%lld",&a[i]);
e.v = abs(a[i]);
e.s = (a[i]<0);
e.pos = i;
q.push(e);
if(a[i]<0) flag = !flag;
}
}
void solve()
{
while(k--)
{
node e = q.top();
q.pop();
if(!flag)
{
e.v -= x;
if(e.v<0)
{
e.v = -e.v;
e.s = !e.s;
flag = !flag;
}
}
else
{
e.v += x;
}
a[e.pos] = e.v;
if(e.s) a[e.pos] = -a[e.pos];
q.push(e);
}
for(int i = 1; i<=n; i++)
printf("%lld ",a[i]);
putchar('
');
}
int main()
{
// int T;
// scanf("%d",&T);
// while(T--)
{
init();
solve();
}
return 0;
}