【rqnoj】pid9 / 佳佳的魔法照片-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心

苦海澜石

凯发app官方网站首页　| 　博文目录　| 　关于我

khls27

  • 博客访问： 752885
  • 博文数量： 144
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1150
  • 用 户 组： 普通用户
  • 注册时间： 2014-03-17 14:32
个人简介

小公司研发总监，既当司令也当兵！

文章分类

全部博文（144）

推荐博文
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
【rqnoj】pid9 / 佳佳的魔法照片

分类： 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>

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

  13. people_t *genpeople(int *wtlist, int len)
  14. {
  15.     int i = 0;
  16.     people_t *root = null;
  17.     people_t *last = null;
  18.     people_t *tmp;

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

  42. people_t *peoplesort(people_t *root, int *extwt, int step)
  43. {
  44.     people_t *head = null;
  45.     people_t *pnode;
  46.     people_t *pnext;

  48.     if (!root)
  49.     {
  50.         return null;
  51.     }
  52.     head = root;
  53.     pnext = root->next;
  54.     head->next = null;

  56.     while (pnext)
  57.     {
  58.         people_t* pcur;
  59.         people_t* pcurnext;
  60.         int nwight;
  61.         int hwight;

  63.         pnode=pnext;
  64.         pnext = pnode->next;
  65.         pnode->next = null;

  67.         nwight = step < 2 ? pnode->wight : (pnode->wight pnode->extwt);
  68.         hwight = step < 2 ? head->wight : (head->wight head->extwt);
  69.         if ((nwight > hwight) || (nwight== hwight && pnode->index < head->index))
  70.         {
  71.             pnode->next = head;
  72.             head = pnode;
  73.             continue;
  74.         }
  75.         pcur = head;
  76.         pcurnext = head->next;
  77.         while (pcurnext)
  78.         {
  79.             hwight = step < 2 ? pcurnext->wight : (pcurnext->wight pcurnext->extwt);
  80.             if ((nwight > hwight) || (pnode->wight == pcurnext->wight && pnode->index < pcurnext->wight))
  81.             {
  82.                 break;
  83.             }
  84.             pcur = pcur->next;
  85.             pcurnext = pcurnext->next;
  86.         }
  87.         pnode->next = pcur->next;
  88.         pcur->next = pnode;
  89.     }

  91.     if (step == 2)
  92.     {
  93.         return head;
  94.     }
  95.     pnext = head;
  96.     while (pnext)
  97.     {
  98.         pnext->extwt = extwt[(pnext->index -1)%10];

  100.         pnext = pnext->next;
  101.     }
  102.     return head;
  103. }

  105. void maxwightn(int *wtlist, int len, int *extwt, int n)
  106. {
  107.     int i = 0;
  108.     people_t *ptr;
  109.     people_t *root;
  110.     root = genpeople(wtlist,len);
  111.     root = peoplesort(root, extwt, 1);
  112.     root = peoplesort(root, extwt, 2);

  114.     ptr = root;
  115.     while (i < n && ptr)
  116.     {
  117.         printf("%d", ptr->index);
  118.         ptr=ptr->next;
  119.         i;
  120.     }
  121. }

  123. int main(int argc, char** argv)
  124. {
  125.     int list[] ={1, 2, 3 ,4, 5, 6, 7, 8, 9, 10};
  126.     int ext[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
  127.     maxwightn(list, 10, ext, 10);
  128. }

阅读(2550) | 评论(0) | 转发(0) |
0

上一篇：【rqnoj】pid21 / fbi树

下一篇：【rqnoj】pid17 / 过河

给主人留下些什么吧！~~
| | | | |

凯发app官方网站 copyright 2001-2010 chinaunix.net all rights reserved 北京皓辰网域网络信息技术有限公司. 凯发k8官网下载客户端中心的版权所有

感谢所有关心和支持过chinaunix的朋友们
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图