首页 > 其他 > 详细

CF1042C Array Product 分类讨论+贪心

时间:2018-10-19 23:31:05      阅读:46      评论:0      收藏:0      [点我收藏+]

标签:个数   rem   \n   div   product   ++   stream   一个数   pen   

技术分享图片

考虑有无负数(负数的个数为奇视作“有”,否则为“无”)和有无零

无负数无零,全部合并即可

无负数有零,那么把零合并起来,删掉零

有负数无零,把最大的负数找出来,删掉,合并剩余的数

有负数有零,把零和最大的负数合并起来,删掉,合并剩余的数

注意如果只剩下一个数,不能删掉这唯一的一个数

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
namespace remoon {
    #define ri register int
    #define ll long long
    #define tpr template <typename ra>
    #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++)
    #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --)    
    #define gc getchar
    inline int read() {
        int p = 0, w = 1; char c = gc();
        while(c > 9 || c < 0) { if(c == -) w = -1; c = gc(); }
        while(c >= 0 && c <= 9) p = p * 10 + c - 0, c = gc();
        return p * w;
    }
    int wr[50], rw;
    #define pc(iw) putchar(iw)
    tpr inline void write(ra o, char c = \n) {
        if(!o) pc(0);
        if(o < 0) o = -o, pc(-);
        while(o) wr[++ rw] = o % 10, o /= 10;
        while(rw) pc(wr[rw --] + 0);
        pc(c);
    }
    tpr inline void cmin(ra &a, ra b) { if(a > b) a = b; }
    tpr inline void cmax(ra &a, ra b) { if(a < b) a = b; } 
    tpr inline bool ckmin(ra &a, ra b) { return (a > b) ? a = b, 1 : 0; }
    tpr inline bool ckmax(ra &a, ra b) { return (a < b) ? a = b, 1 : 0; }
}
using namespace std;
using namespace remoon;
#define sid 300050

int n, a[sid];

inline void Solve1() {
    rep(i, 2, n) printf("1 %d %d\n", i, 1);
}

inline void Solve2() {
    
    int mip = -1e9 - 5, pos = 0;
    rep(i, 1, n) 
    if(a[i] < 0 && ckmax(mip, a[i])) pos = i;
    
    int fir = -1;
    rep(i, 1, n) if(pos != i) { fir = i; break; }
    if(fir == -1) return;
    
    printf("2 %d\n", pos);
    if(pos != 1) {
        rep(i, 2, n) 
        if(pos != i) printf("%d %d %d\n", 1, i, 1);
    }
    else rep(i, 3, n) printf("%d %d %d\n", 1, i, 2);
    
}

inline void Solve3() {
    
    int lst = -1;
    rep(i, 1, n) if(a[i] == 0) {
        if(lst != -1) printf("%d %d %d\n", 1, lst, i);
           lst = i;
    }
    
    int fir = -1;
    rep(i, 1, n) if(a[i] != 0) { fir = i; break; }
    if(fir == -1) return;
    
    printf("2 %d\n", lst);
    rep(i, fir + 1, n) if(a[i] != 0)
    printf("%d %d %d\n", 1, i, fir);

}

inline void Solve4() {
    
    int mip = -1e9 - 5, pos = 0;
    rep(i, 1, n) 
    if(a[i] < 0 && ckmax(mip, a[i])) pos = i;
    
    int lst = -1;
    rep(i, 1, n) if(a[i] == 0 || pos == i) {
        if(lst != -1)  printf("%d %d %d\n", 1, lst, i);
        lst = i;
    }
    
    int fir = -1;
    rep(i, 1, n) if(a[i] != 0 && pos != i) 
    { fir = i; break; }
    if(fir == -1) return;
    
    printf("2 %d\n", lst);
    rep(i, fir + 1, n) if(a[i] != 0 && pos != i)
    printf("%d %d %d\n", 1, i, fir);

}

int main() {
    
    n = read();
    rep(i, 1, n) a[i] = read();
    
    int neg = 0, zero = 0;
    rep(i, 1, n) if(a[i] < 0) neg ^= 1;
    else if(a[i] == 0) zero |= 1;
    
    if(!zero && !neg) Solve1();
    else if(!zero && neg) Solve2();
    else if(zero && !neg) Solve3();
    else if(zero && neg) Solve4();
    
    return 0;
}

 

CF1042C Array Product 分类讨论+贪心

标签:个数   rem   \n   div   product   ++   stream   一个数   pen   

原文:https://www.cnblogs.com/reverymoon/p/9819257.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号