欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言:搬书

程序员文章站 2024-03-18 22:59:46
...

题目描述

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;
}

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