• 博客访问： 670865
• 博文数量： 141
• 博客积分： 0
• 博客等级： 民兵
• 技术积分： 1114
• 用 户 组： 普通用户
• 注册时间： 2014-03-17 14:32

2017-07-16 21:00:05

[题目描述]

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. {
41.     people_t *pnode;
42.     people_t *pnext;

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

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);
61.         if ((nwight > hwight) || (nwight== hwight && pnode->index < head->index))
62.         {
65.             continue;
66.         }
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.     {
85.     }
87.     while (pnext)
88.     {
89.         pnext->extwt = extwt[(pnext->index -1)%10];

90.         pnext = pnext->next;
91.     }
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. }

0