22. 打包礼物

￡神魔★判官ぃ 2022-04-02 07:40 215阅读 0赞

Description

再过一段时间就是龙龙心心念念的她的生日，龙龙准备了k

个礼物送给她，并且决定用顺丰快递寄过去。

但是龙龙发现，因为k

太大了，所以要发很多个快递，这样就要很多的快递费。但是作为一个死肥宅，龙龙还要省点钱去买DELL的显示器、Cherry的机械键盘、NVIDA的最新煤气罐GTX2080呢……所以龙龙感觉钱不够了。

每一个礼物都被包装的明明白白，第

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70][]

#include "stdio.h"
    #include "stdlib.h"
    struct _liwu{
        int v;
        int id;
    }liwu[100005];
    int p[100005][3];
    int cmp(const void *p1, const void *p2){
        struct _liwu *c = (struct _liwu*)p1;
        struct _liwu *d = (struct _liwu*)p2;
        return d->v - c->v;
    }
    int shuchu(int i){
        
        if(p[i][0]!=-1){
            
            shuchu(p[i][0]);
        }
        printf(" %d", liwu[i].id + 1);
        return 0;
    }
    int main()
    {
        int count = 0;
        int k;
        scanf("%d", &k);
        for(int i = 0; i < k; i++){
            scanf("%d", &liwu[i].v);
            liwu[i].id = i;
        }
        qsort(liwu, k, sizeof(struct _liwu), cmp);
        //依次代表装着的礼物的下标，一共装着几个礼物，该礼物是否已经被装(0为被装了)
        for (int i = 0; i < k; i++){
            p[i][0] = -1;
            p[i][1] = 0;
            p[i][2] = -1;
        }
        int m = k - 2;
        for (int i = k - 1; i >= 0; i--){
            for (int j = m; j >= 0; j--){
                if(liwu[j].v >= (liwu[i].v*2)){
                    count++;
                    p[j][0] = i;
                    p[j][1] = p[i][1] + 1;
                    p[i][2] = 0;
                    m = j - 1;
                    break;
                }
                if(j == 0 && liwu[j].v < (liwu[i].v*2)){
                    goto q;
                }
            }
        }
        
    
        q:
    
            printf("%d\n", k - count);
            for (int i = 0; i < k; i++){
                if(p[i][1] == 0 && p[i][2] == -1){//没有被装没有装别人
                    printf("1 %d\n",liwu[i].id+1);
                    continue;
                }
                if(p[i][0]!=-1 && p[i][2]!=0){//
                    printf("%d", p[i][1] + 1);
                    shuchu(p[i][0]);
                    printf(" %d", liwu[i].id+1);
                    putchar('\n');
                    continue;
                }
            }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70]: /images/20220402/5faa34636fc94f8eb1c2c7c9f2d5c2cf.png