Codeforces Round #374 (Div. 2) D. Maxim and Array 贪心

D. Maxim and Array

题目连接:

http://codeforces.com/contest/721/problem/D

Description

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.

Input

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.

Output

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.

Sample Input

5 3 1

5 4 3 5 2

Sample Output

5 4 3 5 -1

Hint

题意

给你n个数,你可以操作k次,每次使得一个数增加x或者减小x

你要使得最后所有数的乘积最小,问你最后这个序列长什么样子。

题解:

贪心,根据符号的不同,每次贪心的使得一个绝对值最小的数减去x或者加上x就好了

这个贪心比较显然。

假设当前乘积为ANS,那么你改变a[i]的大小的话,那么对答案的影响为ANS/A[i]/*X

然后找到影响最大的就好了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7; long long a[maxn],b[maxn];
int n,k,x;
set<pair<long long,long long> >S;
int main()
{
scanf("%d%d%d",&n,&k,&x);
int sig = 0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(a[i]<0)sig^=1;
S.insert(make_pair(abs(a[i]),i));
}
for(int i=1;i<=k;i++)
{
int pos = S.begin()->second;
S.erase(S.begin());
if(a[pos]<0)sig^=1;
if(sig)a[pos]+=x;
else a[pos]-=x;
if(a[pos]<0)sig^=1;
S.insert(make_pair(abs(a[pos]),pos));
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl; }
上一篇:对用户控件(ascx)属性(property)赋值


下一篇:【iCore4 双核心板_FPGA】例程十:FSMC总线通信实验——复用地址模式