题目链接 ：http://codeforces.com/contest/721/problem/D
题目大意：给出n个整数,最多进行k次操作,每次选择一个整数让它+x或者-x,要让最后所有数的乘积最小。
题解：
这题网络上的题解包括官方题解 的证明感觉都是有点问题,只说了每次取最优,但是没说这样可以保证最终答案是最优的。所以我自己来胡扯一个。。
1.先来考虑一个简化版： 所有数都是正整数,每次只能+x,让最后乘积最大。 贪心策略是每次选择最小的那个数使它+x。 证明：可以把a+x的结果看成是原来的乘积prod再乘上一个数$frac{a+x}{a}=1+frac{x}{a}$ 显然a越小越优，且可以保证全局最优。
2.再来看这道题。如果一开始所有数的乘积已经是负数,那么只要绝对值最大，显然不必改变每个数的符号,就转化为上面的问题了。
如果一开始的乘积是正数或者0,我们要想办法把它变成负的。只要把一个正数减小成负的 或者把一个正数增大成正的就好。 可以证明最优方案最多改变一个数的符号。 (假设a,b,c都改变了符号,而 假设b由负变正加了k1个x,c由正变负减了k2个x,实际上如果只改变a的符号,而让b减去k1个x,c加上k2个x 更加优。)
下面证明 改变绝对值最小的那个数的符号是最优的。假设绝对值最小的是a，现在如果我们改变b的符号,b的绝对值比a小。 如果所需的步数一样,那么改变符号后a的绝对值更大,所以改变a更加优。如果改变b的符号所需要的步数比a多,设改变a所需k1步,改变b所需k2步,k2>k1. 如果对a也做k2次操作,会更加优（见我的草稿）
一个超级简单的实现代码：
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cstdlib> #include <set> using namespace std; #define X first #define Y second #define Mod 1000000007 #define N 200010 #define M 200010 typedef long long ll; typedef pair<int,int> pii; int n,k,x; ll a[N]; set< pair<ll,int> > st; int main() { //freopen("in.in","r",stdin); //freopen("out.out","w",stdout); int op=1,pos; ll val; scanf("%d%d%d",&n,&k,&x); for (int i=1;i<=n;i++) { scanf("%I64d",&a[i]); if (a[i]<0) op=-op; st.insert(make_pair(abs(a[i]),i)); } while (k--) { pos=st.begin()->Y; val=st.begin()->X; if (a[pos]<0) op=-op; if (op==-1) a[pos]+=x; else a[pos]-=x; st.erase(st.begin()); st.insert(make_pair(abs(a[pos]),pos)); if (a[pos]<0) op=-op; } for (int i=1;i<=n;i++) printf("%I64d ",a[i]); printf(" "); return 0; }