2018年ブルーブリッジカップc/c++B組初戦(第9回)第10題-積算最大

10.タイトル:積が最大
N個の整数A 1,A 2,…ANが与えられる.その中からK個の数を選んで、その積を最大にしてください.
最大の積を求めてください.積が整数範囲を超えている可能性があるので、積を1000000009で割った残高を出力するだけです.
なお、X<0の場合、Xを1000000009で割った剰余は、負(-X)を1000000009で割った剰余であると定義する.すなわち、0-((0-x)%1000000009)
第1の行は、2つの整数NおよびKを含む.以下のN行は行ごとに1つの整数Aiである.
40%のデータに対して、1<=K<=N<=100は60%のデータに対して、1<=K<=1000は100%のデータに対して、1<=K<=N<=100000-1000<=Ai<=100000
【出力フォーマット】整数で、答えを表します.
【入力サンプル】5 3-100000-100000 2 100000 10000
【出力サンプル】99910009
さらに、例えば、【入力サンプル】5 3-100,000-100,000-2-100,000-100,000
【出力サンプル】-9999999829
リソース約定:ピークメモリ消費量(仮想マシンを含む)<256 M
CPU消費<1000 ms
分析:貪欲な思想で考える
まずデータを処理し、正数を大から小に並べ、負数を絶対値サイズ、大から小に並べ替え、
そして全てのデータにおいて、絶対値の前Kの数字を乗算し、
得られた積が正数であれば最大値となり、型取り出力となる.
積が負の場合は、次の2つのケースがあります.
1.与えられた数字に正数がある場合、積は負数であるが、正数や負数が使われていないものもある.
積に乗じた絶対値の最小の負数を残りの数の最大の正数に置き換えることができ、
あるいは積に乗じた最小の正数を余剰数の絶対値が最大の負数に変換し、
積を正数にし、最大のものを比較して型取り出力します.
2.与えられた数字に負数しかない場合、積が負数であるのは、Kが奇数であり、奇数個の負数が乗算されるか、負数であるかのためである.
このとき、再び数値サイズで数字を並べ替え、前のK個の数値積をとる.

#include
using namespace std;
int a[100005];
int z[100005];
int f[100005];
bool cmp(int a,int b){//         
    return abs(a)>abs(b);
}
bool cmp1(int a,int b){//        
    return a>b;
}
int main(){
    int n,k;
    cin>>n>>k;
    int k1=k;
    int t1=0,t2=0;
    for(int i=0;i0)//               
           z[t1++]=a[i];
        if(a[i]<0)
           f[t2++]=a[i];
    }
    sort(z,z+t1,cmp);//    ，    
    sort(f,f+t2,cmp);//         ，      
    long long ans=1;//     
    int i1=0,i2=0;
    while(1){
        if(k==0)// k  ，      
           break;
        if(abs(z[i1])>abs(f[i2])){//          ，   
            ans*=z[i1];
            i1++;//       。          
            k--;//  
        }
        else{//          ，   
            ans*=f[i2];
            i2++;//       。          
            k--;//  
        }
    }
    if(ans>0){//        0，   10^9+9     
    printf("%lld
",ans%1000000009);
    }
    if(ans<0&&t1!=0){//      0，         ,     ，              ，       
        long long ans1=0;
        if(i1ans)
           printf("%lld",ans1%1000000009);
        else{
            printf("%lld",ans%1000000009);
        }
    }
    if(ans<0&&t1==0){//         ，                  
        sort(f,f+t2,cmp1);//        
        long long ans2=1;
        for(int i=0;i