【RQNOJ】PID9 / 佳佳的魔法照片

[题目描述]

一共有n个人（以1--n编号）向佳佳要照片，而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序，每人就有了一个序号D[i]（取值同样是1--n）。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1，显然类别序号的取值为1--10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后，最终的权值最大的k个人，并输出他们的编号。权值都是正整数。在排序中，如果两人的W[i]相同，编号小的优先。

分析：
该题目主要是考察链表排序，对于链表排序，实现上最简单的就是插入排序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct PEPOLE_NODE {
    int index;
    int wight;
    int extwt;
    struct PEPOLE_NODE* pre;
    struct PEPOLE_NODE* next;
}people_t;

people_t *genPeople(int *wtlist, int len)
{
    int i = 0;
    people_t *root = NULL;
    people_t *last = NULL;
    people_t *tmp;

    for(i=0; i < len; i++)
    {
        tmp = (people_t*) calloc(sizeof(people_t), 1);
        tmp->index = i + 1;
        tmp->wight = wtlist[i];
        if (NULL == root)
        {
            root = tmp;
            last = tmp;
            continue;
        }
        last->next = tmp;
        tmp->pre = last;
        last = tmp;
    }
    if (root)
    {
        root->pre = tmp;
    }
    return root;
}

people_t *peopleSort(people_t *root, int *extwt, int step)
{
    people_t *head = NULL;
    people_t *pnode;
    people_t *pnext;

    if (!root)
    {
        return NULL;
    }
    head = root;
    pnext = root->next;
    head->next = NULL;

    while (pnext)
    {
        people_t* pcur;
        people_t* pcurnext;
        int nwight;
        int hwight;

        pnode=pnext;
        pnext = pnode->next;
        pnode->next = NULL;

        nwight = step < 2 ? pnode->wight : (pnode->wight + pnode->extwt);
        hwight = step < 2 ? head->wight : (head->wight + head->extwt);
        if ((nwight > hwight) || (nwight== hwight && pnode->index < head->index))
        {
            pnode->next = head;
            head = pnode;
            continue;
        }
        pcur = head;
        pcurnext = head->next;
        while (pcurnext)
        {
            hwight = step < 2 ? pcurnext->wight : (pcurnext->wight + pcurnext->extwt);
            if ((nwight > hwight) || (pnode->wight == pcurnext->wight && pnode->index < pcurnext->wight))
            {
                break;
            }
            pcur = pcur->next;
            pcurnext = pcurnext->next;
        }
        pnode->next = pcur->next;
        pcur->next = pnode;
    }

    if (step == 2)
    {
        return head;
    }
    pnext = head;
    while (pnext)
    {
        pnext->extwt = extwt[(pnext->index -1)%10];

        pnext = pnext->next;
    }
    return head;
}

void maxWightN(int *wtlist, int len, int *extwt, int N)
{
    int i = 0;
    people_t *ptr;
    people_t *root;
    root = genPeople(wtlist,len);
    root = peopleSort(root, extwt, 1);
    root = peopleSort(root, extwt, 2);

    ptr = root;
    while (i < N && ptr)
    {
        printf("%d", ptr->index);
        ptr=ptr->next;
        i++;
    }
}

int main(int argc, char** argv)
{
    int list[] ={1, 2, 3 ,4, 5, 6, 7, 8, 9, 10};
    int ext[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    maxWightN(list, 10, ext, 10);
}