Chinaunix首页 | 论坛 | 博客
  • 博客访问: 739948
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1115
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,既当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2017-07-16 21:00:05


[题目描述]

一共有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]相同,编号小的优先。


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

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct PEPOLE_NODE {
  5.     int index;
  6.     int wight;
  7.     int extwt;
  8.     struct PEPOLE_NODE* pre;
  9.     struct PEPOLE_NODE* next;
  10. }people_t;

  11. people_t *genPeople(int *wtlist, int len)
  12. {
  13.     int i = 0;
  14.     people_t *root = NULL;
  15.     people_t *last = NULL;
  16.     people_t *tmp;

  17.     for(i=0; i < len; i++)
  18.     {
  19.         tmp = (people_t*) calloc(sizeof(people_t), 1);
  20.         tmp->index = i + 1;
  21.         tmp->wight = wtlist[i];
  22.         if (NULL == root)
  23.         {
  24.             root = tmp;
  25.             last = tmp;
  26.             continue;
  27.         }
  28.         last->next = tmp;
  29.         tmp->pre = last;
  30.         last = tmp;
  31.     }
  32.     if (root)
  33.     {
  34.         root->pre = tmp;
  35.     }
  36.     return root;
  37. }

  38. people_t *peopleSort(people_t *root, int *extwt, int step)
  39. {
  40.     people_t *head = NULL;
  41.     people_t *pnode;
  42.     people_t *pnext;

  43.     if (!root)
  44.     {
  45.         return NULL;
  46.     }
  47.     head = root;
  48.     pnext = root->next;
  49.     head->next = NULL;

  50.     while (pnext)
  51.     {
  52.         people_t* pcur;
  53.         people_t* pcurnext;
  54.         int nwight;
  55.         int hwight;

  56.         pnode=pnext;
  57.         pnext = pnode->next;
  58.         pnode->next = NULL;

  59.         nwight = step < 2 ? pnode->wight : (pnode->wight + pnode->extwt);
  60.         hwight = step < 2 ? head->wight : (head->wight + head->extwt);
  61.         if ((nwight > hwight) || (nwight== hwight && pnode->index < head->index))
  62.         {
  63.             pnode->next = head;
  64.             head = pnode;
  65.             continue;
  66.         }
  67.         pcur = head;
  68.         pcurnext = head->next;
  69.         while (pcurnext)
  70.         {
  71.             hwight = step < 2 ? pcurnext->wight : (pcurnext->wight + pcurnext->extwt);
  72.             if ((nwight > hwight) || (pnode->wight == pcurnext->wight && pnode->index < pcurnext->wight))
  73.             {
  74.                 break;
  75.             }
  76.             pcur = pcur->next;
  77.             pcurnext = pcurnext->next;
  78.         }
  79.         pnode->next = pcur->next;
  80.         pcur->next = pnode;
  81.     }

  82.     if (step == 2)
  83.     {
  84.         return head;
  85.     }
  86.     pnext = head;
  87.     while (pnext)
  88.     {
  89.         pnext->extwt = extwt[(pnext->index -1)%10];

  90.         pnext = pnext->next;
  91.     }
  92.     return head;
  93. }

  94. void maxWightN(int *wtlist, int len, int *extwt, int N)
  95. {
  96.     int i = 0;
  97.     people_t *ptr;
  98.     people_t *root;
  99.     root = genPeople(wtlist,len);
  100.     root = peopleSort(root, extwt, 1);
  101.     root = peopleSort(root, extwt, 2);

  102.     ptr = root;
  103.     while (i < N && ptr)
  104.     {
  105.         printf("%d", ptr->index);
  106.         ptr=ptr->next;
  107.         i++;
  108.     }
  109. }

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

阅读(2503) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~