codeforces 374 div2 D. Maxim and Array

問題

問題概要

数列aが与えられる。この数列の積を最小に知るために、k回数列の数字を+xまたは、-xすることができる。どのように数列を変えるかを求めよ。

解法

重要な考察が、数列のすべての数字の積を大きくするには、一番小さい数字を大きくしていけばいいということと、積がマイナスになることができるなら、マイナスにするほうがいいということ。
実装は、まず、与えらた数列に負の数がいくつあるかを求め、その数が奇数であれば、すでに積がマイナスなので、あとは、k回分数列の中で、絶対値が一番小さい数を大きくするように処理すればいい。絶対値が一番小さいやつを求めるのにはpriority_queueを用いればよい。また、偶数の場合は、一番絶対値が小さい数を1つ、符号を変える。符号を変えれる場合(abs(mi) < k * x)は、符号を変えて、残りの回数だけ、もともと積が負の場合と同じ処理をすればいい。絶対値が一番小さい数字でさえ符号を変えられない場合は、絶対値が一番小さい数字の絶対値を小さくするように、その数からk*xを足すか引けばよい。これは、積を大きくするには、一番小さい数字を大きくしていくのだから、逆に考えると、積を小さくしていくには、一番小さい数字を小さくしていけばよい。

ミス

考察が厳しいね。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
const ll INF = 1e12;

int n, k;
ll x;
ll a[200010];

void absmax(void){
    priority_queue<P, vector<P>, greater<P> > q;
    rep(i, n){
        q.push(make_pair(abs(a[i]), i));
    }
    //絶対値が小さいものから優先的に大きくしていく
    rep(i, k){
        auto tmp = q.top(); q.pop();
        int idx = tmp.second;
        if(a[idx] >= 0){
            a[idx] += x;
            q.push(make_pair(abs(a[idx]), idx));
        }else{
            a[idx] -= x;
            q.push(make_pair(abs(a[idx]), idx));
        }
    }
    return;
}

int main(void){
    cin >> n >> k >> x;
    ll sign = 0;
    ll mi = INF;
    int miidx;
    rep(i, n){
        cin >> a[i];
        if(a[i] < 0) sign++;
        if(abs(a[i]) < abs(mi)){
            mi = a[i];
            miidx = i;
        }
    }
    sign %= 2;

    if(sign == 1){//現在積は負
        absmax();
    }else{//現在積は正
        if(abs(mi) < k * x){//一番小さいものの符号を変えられる
            //絶対値が一番小さいものの符号を変える
            if(mi >= 0){
                while(a[miidx] >= 0){
                    a[miidx] -= x;
                    k--;
                }
                absmax();
            }else{
                while(a[miidx] <= 0){
                    a[miidx] += x;
                    k--;
                }
                //符号を変えて全部の積でマイナスになったら、次は絶対値で一番小さいものの絶対値を小さくしていけばいい
                absmax();
            }
        }else{//一番小さいものの符号を変えられない
            //絶対値が一番小さいものの絶対値を小さくすればいい
            if(mi >= 0){
                a[miidx] -= k * x;
            }else{
                a[miidx] += k * x;
            }
        }
    }

    rep(i, n){
        printf("%lld ", a[i]);
    }
    printf("\n");
}