蓝桥杯 纪念品分组 （快排+贪心）----------C语言—菜鸟级

/*问题描述
　　元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得
的纪念品价值 相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时 间内发完所有纪念品，乐乐希望分组的数目最少。
　　你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入格式
　　输入包含n+2行：
　　第1行包括一个整数w，为每组纪念品价格之和的上限。
　　第2行为一个整数n，表示购来的纪念品的总件数。
　　第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
输出格式
　　输出仅一行，包含一个整数，即最少的分组数目。
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
数据规模和约定
　　50%的数据满足：1 <= n <= 15
　　100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
思路： 快排一波 再从大到到小 开始分组 最大的物品 加最小的物品 超出限制则
最大单独 一组 否则 两物品成一组 详情 见代码

*/

 #include <stdio.h>
 long int p[30001];//物品 
 void jh(int x,int y) 
 {int m=p[x];
     p[x]=p[y];
     p[y]=m;
 }
 int p1(int ks,int js)
 {
 	int max=p[ks];
 	int i1=ks;
 	int j1=js+1;
 	while(1)
 	{ while(p[++i1]>max&&i1<js);
 	   while(p[--j1]<max);
 	   if(i1>=j1)break;
 	   jh(i1,j1);
 		
 	}
 	jh(ks,j1);
 	return j1;
 }
 void q(int ks,int js)
 {int r;
       if(ks<js)
	   {   r=p1(ks,js);
	       q(ks,r-1);
	       q(r+1,js);
       }
 	
 }
 
 //以上为 快排部分 
 
 int main()
 {
 long int n,w,i,j,sum=0;
 scanf("%ld%ld",&w,&n);
 
 for(i=0;i<n;i++)
   {scanf("%ld",&p[i]);
     if(w-p[i]<5){i--;n--;sum++;}//优化 因为 有 (5 <= pi <= w)条件 所以  
   }                             //    物品距上线不足5就只能独立一组
   q(0,n-1);//全排 
   for(i=0;i<n;i++)
  if((p[i]+p[n-1])>w&&i!=n-1)sum++;//超出上限或 当前最大最小是同一件物品 最大单组 
        else sum++,n--;//未超出则 当前最大最小 同时取出（末端n--;) 
  	printf("%ld\n",sum);
 return 0;
 }

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80031500