What is the Codeforces Round schedule for upcoming competitions?

本文共计996个文字，预计阅读时间需要4分钟。

题目链接：http://codeforces.com/problemset/problem/721/D题目：Maxim and Array时间限制：每题2秒内存限制：每题256兆字节输入：标准输入输出：标准输出

题目描述：给定一个数组，找出一个子数组，使得该子数组的最大值与最小值的差值最大。输出这个最大差值。

题目链接codeforces.com/problemset/problem/721/D

D. Maxim and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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.

Examples input

5 3 15 4 3 5 2 output

5 4 3 5 -1 input

5 3 15 4 3 5 5 output

5 4 0 5 5 input

5 3 15 4 4 5 5 output

5 1 4 5 5 input

3 2 75 4 2 output

5 11 -5

题解

1.首先在输入时统计负数的个数目的是知道初始状态的乘积是正数包括0还是负数。

2.如果乘积为正数那么就需要减小某个数的绝对值使其改变符号 而且步数越少越好由此推出减少绝对值最小的那个数的绝对值可以最快改变符号使得乘积变为负数。

3.如果乘积已经为负那么就需要增加某个数的绝对值 使得乘积的绝对值尽可能大 根据基本不等式 ab>2*根号a*b若要a*b的值最大则ab。 可以得出结论当a与b的差值越小时a*b越大。或者可以自己手动推算一遍 也可以得出这个结论。由此推出增加绝对值最小的那个数的绝对值使得乘积的绝对值尽可能大。

4.总的来说就是需要对绝对值最小的数进行操作。当乘积为正或为0时 减小其绝对值直到符号改变 当乘积为负时 增加其绝对值 使其乘积的绝对值尽可能大。 用优先队列维护。

学习之处 

ab常数 当a与b的差值越小时a*b越大a*b>0。

这里的a*b可以假设a为绝对值最小的那个数 b为其他数的绝对值的乘积。所以这个结论也适用于多个数的乘积将多个转为2个。

代码如下

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define ms(a, b) memset((a), (b), sizeof(a))#define eps 0.0000001typedef long long LL;const int INF 2e9;const LL LNF 9e18;const int mod 1e97;const int maxn 2e510;struct node{LL v, s, pos;bool operatorx.v;}};priority_queueq;LL a[maxn], n, k, x, flag;void init(){scanf("%lld%lld%lld",while(!q.empty()) q.pop();flag 0;for(int i 1; i

转:www.cnblogs.com/DOLFAMINGO/p/7538692.html