C语言：搬书

题目描述

XCQ队长要退役啦，由于队长常年刷题，机位上摆着各类算法书，一个人实在是搬不动，所以他叫来了他的小弟ZZX帮忙搬书。队长突然灵机一动，给ZZX出了一个问题。

假设机位上有n本书，每本书的体积分别为ai，那么如果使用容量为V的书包来装书最少要几个书包呢？(注意书是不可拆分的，整体要么装到一个书包，要么不装)。

ZZX(冥思苦想)：不会呀。

XCQ： 看你这么弱，我就把问题再简化一下好啦，让每个书包只装不超过两本书, 那么用k(2 * k >= n)个体积为V的书包能否装完n本书呢？

ZZX(又是一阵冥思苦想): 队长放过我吧，实在是不会啊。

XCQ: 长江后浪推前浪， 既然如此，就把这个问题交给后浪们吧。

输入
第一行包含一个数字T(T <= 60), 表示测试数据组数。然后一空行，随后有T组数据。

每组测数据格式如下：

第一行包含三个数字n，k，V(1 <= n <= 1000000, n <= 2 * k <= 1000000, 1 <= V <= 1000000),表示有n本书，使用k个容量为V的书包。

第二行n个数,表示每本书的体积ai(ai <= 1000000)。所有数据保证给出的n个数是非递减的。

每组数据后面有一空行。

输出

每组数据输出一行, 如果能够装完所有书本输出"Yes"，否则输出"No"，引号不需要输出，注意字母大小写。

样例输入
3

4 5 8
1 5 6 8

3 2 7
3 5 7

10 5 108
15 15 20 28 38 44 46 52 69 94

样例输出
Yes
No
No

附上我最开始写的错误的代码，提交上去显示的是：运行错误，也就是说我的数组下标越界了，但是我没有检查出来，看出来的小伙伴告诉我一声哈~~

#include <stdio.h>
#define REP(a,b) {int s=a; a=b; b=s;}
void fuc(int vbook[],int n,int v,int k)	
{
    int i,j,bags=0;
    for(i=n-1;i>=1;i--)
	{
        for(j=i-1;j>=0,vbook[i]!=0;j--)
	    {
		    if( vbook[i]+vbook[j]<=v )
		    {
			    bags ++;
			    vbook[j]=0;
			    REP(vbook[j],vbook[i-1]);
			    break;
		    }
		    if(j==0&&vbook[i]+vbook[j]>v)  bags ++;
	    }
	}
	if(vbook[0]!=0) bags ++;
    printf("%s\n", bags>k? "No":"Yes");	
}
				
int main()
{
    int T,n,k,v;
	scanf("%d",&T);
	for(;T>0;T--)
	{
		scanf("%d%d%d",&n,&k,&v);
		int vbook[n],i;
		int sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&vbook[i]);
			sum +=vbook[i];
		} 
		if((k*v<sum&&n!=1)||vbook[n-1]>v) printf("No\n");
		if(n==1&&vbook[0]<=v)  printf("Yes\n");
		if(k*v>=sum&&vbook[n-1]<=v&&n>1)  fuc(vbook,n,v,k);
	}
	return 0;	
}

这个方法也比较蠢，然后代码特别长，被大佬嫌弃了。。。
问了大佬，然后他就让我看竞赛入门书的贪心法，于是我又重新编了一个，这次终于！终于！终于！做对了！！！！热泪盈眶啊~~代码如下：

#include <stdio.h>
int main()
{
    int T,n,k,v;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&k,&v);
		int vbook[n],i,j,flag=0;
		for(i=0;i<n;i++){
			scanf("%d",&vbook[i]);
			if(vbook[i]>v) { flag=1; continue; }	
		}
		if(flag) printf("No\n");
		else{
		    int j=n,bags=0;
			for(i=0;i<n;i++)
		    {
		    	int k;
			    for(j=j-1,k=j;j>0,j>=i;j--)
		    	{
		    		if(i==j) bags++;
		    		if(vbook[i]+vbook[j]<=v&&i!=j)  
					{
					    bags++; 
						if(j!=k) bags=bags+k-j;
						break;
					}
				    if(vbook[i]+vbook[j]>v&&j==i+1)  { bags=bags+k-i+1; i=n; }
				}
			}
		    printf("%s\n", bags>k? "No":"Yes"); 
		} 
    }
	return 0;
}

搬书这个主要是运用贪心法~